題意#
世界上有 \(n\) 座城市以及 \(m\) 條雙向道路。任務是處理 \(q\) 筆查詢：給定出發城市和目的城市，請算出這兩座城市之間的最短路線長度。如果根本走不到目的地，請輸出 -1。
這一次我們要計算的不再只是單一出發點，而是有高頻率任意兩點的詢問。
思路#
面對需要計算「任意兩點之間」最短路徑的問題，我們馬上就能聯想到全點對最短路（All-Pairs Shortest Path）的唯一霸主：Floyd-Warshall 演算法。
這題看準的就是這點，所以題目的測資也給得很客氣，\(n\) 最大只有 500。Floyd-Warshall 演算法的精髓在於「中繼點（\(k\)）」的枚舉，時間複雜度剛好是 \(O(n^3)\)，處理 500 的立方（約一億次運算）在 C++ 的一秒時間限制內是可以順利過關的。
我們只要一開始建立一張 \(n \times n\) 的相鄰矩陣，將所有距離的初始值設為無限大（INF）。讀入每一條邊時更新成最短的一條（因為可能有重複連線的邊），接著跑經典的 3 層迴圈 k、i、j 狀態轉移：
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
也就是說，「考慮把 \(k\) 當成中繼點，看看從 \(i\) 走到 \(k\) 再走到 \(j\) 會不會比現在從 \(i\) 直接走到 \(j\) 更近？」跑完之後，這張矩陣就會神奇地變成兩兩之間最短距離的終極查詢表。最後的 \(q\) 筆詢問更是直接 \(O(1)\) 查表輸出即可。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
#define INF LONG_LONG_MAX/1000
signed main() { WA();
int n, m, q;
cin >> n >> m >> q;
// 初始化相鄰矩陣，預設距離都是大到靠北的 INF
vector<vector<int>> g(n, vector<int>(n, INF));
while (m--) {
int a, b, w;
cin >> a >> b >> w;
a--; b--; // 將題目給定的 1-based 轉為 0-based 以對齊矩陣
// 一對城市之間可能有多條路，只留長度最短的那條
g[a][b] = g[b][a] = min(g[a][b], w);
}
// Floyd-Warshall 的核心靈魂：最外層迴圈必須是中繼點 k
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 嘗試把 k 當作跳板轉機，看看會不會比 i 直接飛到 j 便宜
g[i][j] = g[j][i] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
// 自己走到自己的距離永遠為 0，這步處理很關鍵，避免負環的干擾並修正初始點
for (int i = 0; i < n; i++) g[i][i] = 0;
// 回答所有詢問
while (q--) {
int a, b; cin >> a >> b;
a--; b--; // 記得同樣轉成 0-based
cout << (g[a][b] == INF ? -1 : g[a][b]) << '\n';
}
}
