ACM
2009. 6. 2. 20:56
반응형
Unfortunately, I didn't get accept from Judge Server.
This code is one of my co-worker's source.
He used Dynamic Programming.
I should study that algorithm.
----------------------------------------------------------------------------------------------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <stdio.h> int g_cities[101][101]; #define MIN(a,b) (a>b?b:a) int search_min_trips(int start, int end, int num_cities) { int i, j, k; int max = 0, min; for (i = 1; i <= num_cities; i++) { for (j = 1; j <= num_cities; j++) { for (k = 1; k <= num_cities; k++) { min = MIN(g_cities[i][k], g_cities[k][j]); if (g_cities[i][j] < min) g_cities[i][j] = g_cities[j][i] = min; }}} return g_cities[start][end]; } int main() { int i, cnt = 0; int num_cities; int num_roads; int num_passengers; int start, end; int city1, city2, cap; int max_cap; while (scanf("%d %d", &num_cities, &num_roads) != 1 && num_cities != 0 && num_roads != 0) { memset(g_cities, 0x00, sizeof(g_cities)); for (i = 0; i < num_roads; i++) { scanf("%d %d %d", &city1, &city2, &cap); g_cities[city1][city2] = g_cities[city2][city1] = cap; } scanf("%d %d %d", &start, &end, &num_passengers); max_cap = search_min_trips(start, end, num_cities) - 1; printf("Scenario #%d\n", ++cnt); printf("Minimum Number of Trips = %d\n\n", num_passengers / max_cap + (num_passengers % max_cap == 0 ? 0 : 1)); } return 0; } |
반응형
'ACM' 카테고리의 다른 글
[Accept] 10132 File Fragmentation (0) | 2009.06.02 |
---|---|
[Accept] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Time Limit] 10099 - The Tourist Guide (0) | 2009.06.02 |
[Accept] 10004 - Bicoloring problem (0) | 2009.06.02 |
[Accept] 100 - The 3n+1 problem (0) | 2009.06.02 |