今天的題目是回憶迷宮

這個題目我們來熟悉一下 弗洛伊德算法 的代碼模板
弗洛伊德算法用來處理最短路徑問題

弗洛伊德算法（Floyd’s algorithm）用于解決圖中所有節(jié)點對之間的最短路徑問題。算法的基本思路是通過逐步迭代更新節(jié)點對之間的最短路徑長度，直到得到所有節(jié)點對之間的最短路徑。

以下是弗洛伊德算法的大致思路：

• 初始化距離矩陣：創(chuàng)建一個二維矩陣，稱為距離矩陣，用于存儲節(jié)點對之間的最短路徑長度。初始時，距離矩陣的值為圖中節(jié)點之間的直接距離，如果兩個節(jié)點之間沒有直接邊相連，則距離為無窮大。

• 迭代更新最短路徑：通過遍歷所有節(jié)點，對于每一對節(jié)點 (i, j)，檢查是否存在一個中間節(jié)點 k，使得從節(jié)點 i 到節(jié)點 j 經(jīng)過節(jié)點 k 的路徑長度比直接從 i 到 j 的路徑更短。如果存在這樣的中間節(jié)點 k，則更新距離矩陣中節(jié)點 i 到節(jié)點 j 的最短路徑長度為經(jīng)過節(jié)點 k 的路徑長度。

• 重復(fù)執(zhí)行步驟 2：重復(fù)執(zhí)行步驟 2，直到所有節(jié)點對之間的最短路徑長度都被計算出來，即距離矩陣不再變化。

• 輸出結(jié)果：輸出距離矩陣，其中的每個元素表示對應(yīng)節(jié)點對之間的最短路徑長度。

弗洛伊德算法的核心思想是動態(tài)規(guī)劃。通過逐步迭代更新節(jié)點對之間的最短路徑長度，算法最終得到所有節(jié)點對之間的最短路徑。由于需要遍歷所有節(jié)點和中間節(jié)點，算法的時間復(fù)雜度為 O(n^3)，其中 n 是圖中節(jié)點的數(shù)量。

總的來說就是，建模+核心的3個for循環(huán)

for (int k = 1; k <= n; k++)  // 這個是中間途經(jīng)的點{for (int i = 1; i <= n; i++) {  // 起始點for (int j = 1; j <= n; j++) {  // 終點d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}

最終實現(xiàn)的代碼如下

#include<iostream>using namespace std;
typedef long long ll;const int N = 410;
ll d[N][N];  // 開辟一個數(shù)組存儲信息int n, m, q; // 設(shè)置全局變量void floyd()
{for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}
}int main()
{cin >> n >> m >> q;// 下面要進行初始化操作for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) d[i][j] = 0;else d[i][j] = LLONG_MAX / 2;}}while (m--){ll a, b, c;cin >> a >> b >> c;d[a][b] = d[b][a] = min(d[a][b], c);}floyd();while (q--){int a, b;cin >> a >> b;if (d[a][b] >= LLONG_MAX / 2) cout << "-1" << endl;else cout << d[a][b] << endl;}return 0;
}

有一個小細節(jié)，初始化數(shù)組的時候

d[a][b] = d[b][a] = min(d[a][b], c);

這個要避免有重邊