ZeroJudge 解題筆記：a674. 10048 - Audiophobia

作者：王一哲
日期：2026年1月14日


ZeroJudge 題目連結：a674. 10048 - Audiophobia

解題想法

這題考 Floyd-Warshall 演算法。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 3.8 MB，通過測試。

import sys

result = []
lines = sys.stdin.readlines()
idx = 0
ca = 0  # case number
while idx < len(lines):
    if not lines[idx].strip():
        idx += 1
        continue
    if lines[idx].strip() == "0 0 0":
        break
    C, S, Q = map(int, lines[idx].split())
    idx += 1
    ca += 1
    if result:  # 如果 result 已經有內容，先換行
        result.append("\n")
    result.append(f"Case #{ca:d}\n")
    # 建立儲存節點 u 到 v 噪音值的接鄰矩陣，預設為無窮大，代表不連通
    cost = [[float('inf')]*(C+1) for _ in range(C+1)]
    for i in range(C+1):  # 同一個節點成本為 0
        cost[i][i] = 0
    for _ in range(S):  # 節點 u 到 v 成本
        u, v, d = map(int, lines[idx].split())
        idx += 1
        cost[u][v] = d
        cost[v][u] = d
    # Floyd-Warshall 演算法，以 k 為中繼點，從 i 到 j 的最大噪音值
    for k in range(1, C+1):
        for i in range(1, C+1):
            for j in range(1, C+1):
                if cost[i][k] != float('inf') and cost[k][j] != float('inf'):
                    if cost[i][j] > max(cost[i][k], cost[k][j]):
                        cost[i][j] = max(cost[i][k], cost[k][j])
    # Q 次查詢
    for _ in range(Q):
        u, v = map(int, lines[idx].split())
        idx += 1
        if cost[u][v] == float('inf'):
            result.append("no path\n")
        else:
            result.append(f"{cost[u][v]:d}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <cstdio>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int C, S, Q, ca = 0;
    while(scanf("%d %d %d", &C, &S, &Q) != EOF) {
        if (C == 0 && S == 0 && Q == 0) break;
        ca++;
        if (ca > 1) puts("");
        printf("Case #%d\n", ca);
        vector<vector<int>> cost (C+1, vector<int> (C+1, INT_MAX));
        for(int i=0; i<=C; i++) cost[i][i] = 0;
        for(int i=0; i<S; i++) {
            int u, v, d;
            scanf("%d %d %d", &u, &v, &d);
            cost[u][v] = d;
            cost[v][u] = d;
        }
        for(int k=1; k<=C; k++) {
            for(int i=1; i<=C; i++) {
                for(int j=1; j<=C; j++) {
                    if (cost[i][k] != INT_MAX && cost[k][j] != INT_MAX) {
                        if (cost[i][j] > max(cost[i][k], cost[k][j])) {
                            cost[i][j] = max(cost[i][k], cost[k][j]);
                        }
                    }
                }
            }
        }
        for(int i=0; i<Q; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            if (cost[u][v] == INT_MAX) puts("no path");
            else printf("%d\n", cost[u][v]);
        }
    }
    return 0;
}