alan23273850 的刷題筆記
a674: 10048 - Audiophobia
Tags: floyd-warshall, graph
出處：https://zerojudge.tw/ShowProblem?problemid=a674
提交：https://zerojudge.tw/Submissions?problemid=a674&account=allllllan123456
問題：給定 $C\in[1,100]$ 個點、$S\in[1,1000]$ 條有記錄該區段噪音的無向邊 (不會指回自己)，接下來有 $Q\in[1,10000]$ 筆詢問，給定兩相異起點 C$_1$ 和終點 C$_2$，請問從 C$_1$ 走到 C$_2$ 的全部可能路徑裡面哪一條所必須忍受的最大噪音為最小？其值為何？我們定義一條路徑裡面的最大噪音就是所包含的邊裡面有最大噪音的那一段。
解法：這題的模型滿足 Floyd-Warshall 的適用條件 (詳細解說請參考演算法解說的第一個延伸模型)，只是現在不是要算最短路徑，是要算能讓兩點途中所經過之最大噪音最小化的路徑，那個地方稍微改一下就好。另外，因為初始化有用到 memset，所以是用 0x7f7f7f7f 代表無限大而不是 INT_MAX。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int C, S, Q, cases=0, noise[101][101];
6 while (cin >> C >> S >> Q && (C || S || Q)) {
7 memset(noise, 0x7f, sizeof noise); // 一個 byte 的最大值
8 for (int a, b; S--;)
9 cin >> a >> b >> noise[a][b],
10 noise[b][a] = noise[a][b];
11 for (int k=1; k<=C; k++)
12 for (int i=1; i<=C; i++)
13 for (int j=i+1; j<=C; j++)
14 noise[j][i] = noise[i][j] = min(noise[i][j], max(noise[i][k], noise[k][j]));
15 cout << "Case #" << (++cases) << '\n';
16 for (int a, b; Q--;)
17 cin >> a >> b,
18 cout << ((noise[a][b] == 0x7f7f7f7f) ? "no path" : to_string(noise[a][b])) << '\n';
19 cout << '\n';
20 }
21 return 0;
22}