alan23273850 的刷題筆記
c128: 00544 - Heavy Cargo
Tags: floyd-warshall, graph
出處：https://zerojudge.tw/ShowProblem?problemid=c128
提交：https://zerojudge.tw/Submissions?problemid=c128&account=allllllan123456
問題：給定 $n\in[2,200]$ 個點、$r\in[1,19900]$ 條有記錄該路段重量承受度的無向邊，接下來只有一筆詢問，給定起點 C$_1$ 和終點 C$_2$，請問從 C$_1$ 走到 C$_2$ 的所有可能路徑裡面哪一條的承載重量為最大？其值為何？一條路徑裡面的承載重量就是所包含的邊裡面有最小承載重的那一段。
解法：因為這題每張圖只有一筆詢問，理論上要用 single source shortest path 比較快，但我意外得知 Floyd-Warshall algorithm 也會過，所以就直接把 a674 的程式碼拿來改了。城市名稱對應到點序號可以使用 map 實作。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n, r, cases=0, capacity[201][201];
6 map<string, int> m; string a, b;
7 while (cin >> n >> r && (n || r)) {
8 m.clear(); memset(capacity, 0xff, sizeof capacity); // 設 integer 為 -1
9 for (int i=0; i<r; i++) { cin >> a >> b;
10 try { m.at(a); } catch (...) { m[a] = m.size(); }
11 try { m.at(b); } catch (...) { m[b] = m.size(); }
12 int c = m[a], d = m[b];
13 cin >> capacity[c][d]; capacity[d][c] = capacity[c][d];
14 }
15 for (int k=0; k<n; k++)
16 for (int i=0; i<n; i++)
17 for (int j=i+1; j<n; j++)
18 capacity[j][i] = capacity[i][j] = max(capacity[i][j], min(capacity[i][k], capacity[k][j]));
19 cout << "Scenario #" << (++cases) << '\n';
20 cin >> a >> b;
21 cout << to_string(capacity[m[a]][m[b]]) << " tons\n\n";
22 }
23 return 0;
24}