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
posted by ssuk1010
: