Problem 10048 Audiophobia，噪音恐懼症

此題與 Problem 534 Frogger 用的方法一模一樣，只是這題更簡單了，因為它不需要算點與點之間的距離，它直接給你某路口走到某路口所經過的街道，噪音有多少分貝。

因為這一題有些地方不能直達，所以值還會是 0，所以我初始化就全部給他定 1000，噪音到 1000 分貝，耳膜也破了吧。再接著用最小路徑演算法，答案就會呼之欲出了。

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");
}

By David.K

p10048題目連結
回ACM題庫目錄
回首頁