ACM 10099 - The Tourist Guide

#include <stdio.h>
#include <memory.h>

int min(int a, int b)
{
    return (a < b) ? a: b;
}
 
int max(int a, int b)
{
    return (a > b) ? a: b;
}
int main()
{
    int i, j, k;
    int n, r, p, t;
    int c1, c2;
    int count = 0;
    int city[102][102];
    while(scanf("%d %d", &n, &r) == 2){
        memset(city, 0, sizeof(city));
        if(n == 0 && r == 0)
            break;
        while(r --){
            scanf("%d %d %d", &c1, &c2, &p);
            city[c1][c2] = city[c2][c1] = p;   
        }
        scanf("%d %d %d", &c1, &c2, &t);
        for(k = 1; k <= n; k++)
            for(i = 1; i <= n; i++)
                for(j = 1; j <= n; j++){
                     city[i][j] = max(city[i][j], min(city[i][k], city[k][j]));    
                }
        printf("Scenario #%d\n", ++count);
        printf("Minimum Number of Trips = %d\n\n", 
                        t % (city[c1][c2] - 1) ? t / (city[c1][c2] - 1) + 1: t / (city[c1][c2] - 1));
    }
    return 0;
}

回目錄
回首頁