ACM 10048 - Audiophobia

#include <stdio.h>
#include <memory.h>
#define SIZE 101
int W[SIZE][SIZE];

int min(int n, int m)
{
    return n < m ? n : m;
}

int max(int n, int m)
{
    return n < m ? m : n;
}

int main()
{
    int C, S, Q, i, j, k, caseNum = 1;
    while (scanf("%d %d %d", &C, &S, &Q) == 3 && C && S && Q)
    {
        for (i = 1; i <= C; i ++)
            for (j = 1; j <= C; j ++)
                W[i][j] = 1000;
        
        for (i = 0; i < S; i ++)
        {
            int noise, p1, p2;
            scanf("%d %d %d", &p1, &p2, &noise);
            W[p1][p2] = W[p2][p1] = noise;
        }
        for (k = 1; k <= C; k ++)
            for (i = 1; i <= C; i ++)
                for (j = 1; j <= C; j ++)
                    if (i != j)
                        W[i][j] = min(W[i][j], max(W[i][k], W[k][j]));
        if (caseNum != 1) printf("\n");
        printf("Case #%d\n", caseNum ++);
        for (i = 1; i <= Q; i ++)
        {
            int p1, p2;
            scanf("%d %d", &p1, &p2);
            int minNoise = W[p1][p2];
            if (minNoise != 1000) printf("%d\n", W[p1][p2]);
            else printf("no path\n");
        }
    }
    return 0;
}

回目錄
回首頁