一、學習目標

• 了解 Floyd–Warshall 的狀態定義與三重迴圈轉移，正確處理多重邊與自環。
• 學會在有多組查詢時，用 APSP（All-Pairs Shortest Paths） 一次性解決。
• 熟悉傳遞閉包（Warshall） 與 變形（例如計數、K 次限制等與 Floyd 的取捨）。
• 對比何時選 Floyd (O(n^3)）、何時選 Dijkstra/Bellman–Ford。

二、觀念說明

• 狀態：dist[i][j] 表示 i→j 的目前最短距離；初始化：dist[i][i]=0，無邊為 INF，多重邊取最小權。
• 轉移（核心）：
  dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
  迴圈順序通常為 for k for i for j。
• 複雜度：O(n^3)，適合 n≤500 左右且有大量查詢的情境。
• 不可有負環（標準最短路徑意義會崩壞）。若需偵測負環，可在 Floyd 結束後看 dist[v][v] < 0。
• 傳遞閉包：若只要「可達性」，可以用布林矩陣 + 或（OR）、與（AND）運算替代數值加法/比較。

三、CSES實戰演練

題目1:Shortest Routes II

原題:
https://cses.fi/problemset/task/1672

題意:
給定 n 個點、m 條有向邊、q 個查詢。每個查詢問 a→b 的最短距離；若不可達輸出 -1。

解題思路:

• 任意兩點的最短距離 → Floyd–Warshall。
• 初始化 dist[i][i]=0；對每條邊 u->v 權重 w：dist[u][v] = min(dist[u][v], w)（處理多重邊）。
• 跑完三重迴圈後直接回答查詢；不可達（INF）印 -1。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    const long long INF = (long long)4e18;

    vector<vector<long long>> dist(n+1, vector<long long>(n+1, INF));
    for (int i = 1; i <= n; ++i) dist[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int a, b; long long w;
        cin >> a >> b >> w;
        dist[a][b] = min(dist[a][b], w); // 處理多重邊
    }

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) if (dist[i][k] < INF) {
            for (int j = 1; j <= n; ++j) if (dist[k][j] < INF) {
                long long nd = dist[i][k] + dist[k][j];
                if (nd < dist[i][j]) dist[i][j] = nd;
            }
        }
    }

    while (q--) {
        int a, b; cin >> a >> b;
        long long ans = dist[a][b];
        cout << (ans >= INF/2 ? -1 : ans) << "\n";
    }
    return 0;
}

題目2:Round Trip II

原題:
https://cses.fi/problemset/task/1678

題意:
給一張有向圖，若存在有向環，輸出該環的節點序列；否則輸出 IMPOSSIBLE。

解題思路:

• 用 DFS + 顏色/遞迴棧：0=未訪, 1=遞迴中, 2=已完成。
• 當從 u 走到 v 發現 v 正在遞迴中（顏色 1），就找到了環；沿 parent 往回重建。
• 注意輸出格式：從環的起點一路到自己，再回到起點（首尾一致）。

#include <bits/stdc++.h>
using namespace std;

int main(){
    cin >> n >> m;
    vector<vector<int>> g(n+1);
    for(int i=0;i<m;i++){
        int u,v; cin >> u >> v;
        g[u].push_back(v);
    }

    vector<int> color(n+1,0), parent(n+1,-1);
    int cyc_u=-1, cyc_v=-1;

    function<bool(int)> dfs = [&](int u){
        color[u]=1;
        for(int v: g[u]){
            if(color[v]==0){
                parent[v]=u;
                if(dfs(v)) return true;
            }else if(color[v]==1){
                cyc_u=u; cyc_v=v; // 發現回邊 u->v
                return true;
            }
        }
        color[u]=2;
        return false;
    };

    for(int i=1;i<=n;i++){
        if(color[i]==0 && dfs(i)){
            // 重建環 v ... u -> v
            vector<int> cyc; cyc.push_back(cyc_v);
            for(int x=cyc_u; x!=cyc_v; x=parent[x]) cyc.push_back(x);
            cyc.push_back(cyc_v);
            reverse(cyc.begin(), cyc.end());
            cout << cyc.size() << "\n";
            for(size_t k=0;k<cyc.size();k++)
                cout << cyc[k] << (k+1==cyc.size()?'\n':' ');
            return 0;
        }
    }
    cout << "IMPOSSIBLE\n";
    return 0;
}

四、Leetcode實戰演練

題目1:Cheapest Flights Within K Stops

原題:
https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

題意:
城市 n、航線 flights[u,v,w]，從 src 飛到 dst，最多 K 次中轉（即最多 K+1 段航班）。求最小成本，不能到達回傳 -1。

解題思路:

• 此題是限制邊數的最短路，Floyd/一般 Dijkstra 不直接處理「最多 K 段」。
• 用 Bellman–Ford 的 K+1 次鬆弛（或 DP：dp[t][v] 表示用 t 段到 v 的最小成本）。
• 每一輪用上一輪的結果做鬆弛，避免在同輪連鎖更新。

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        const int INF = 1e9;
        vector<int> dist(n, INF);
        dist[src] = 0;
        // 允許最多 K 次中轉 → 最多 K+1 段邊
        for (int t = 0; t <= K; ++t) {
            vector<int> nd = dist; // 只用上一輪結果
            for (auto &e: flights) {
                int u = e[0], v = e[1], w = e[2];
                if (dist[u] == INF) continue;
                nd[v] = min(nd[v], dist[u] + w);
            }
            dist.swap(nd);
        }
        return dist[dst] >= INF/2 ? -1 : dist[dst];
    }
};

題目2:Find the City With the Smallest Number of Neighbors at a Threshold Distance

原題:
https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

題意:
給定無向加權圖與門檻 distanceThreshold。對每個城市 i，計算所有 dist[i][j] <= threshold 的城市數量（不含自己），回傳 鄰居數最少 的城市；若有多個，回傳 索引較大 的那個。

解題思路:

• 需要任意兩點距離 → Floyd–Warshall。
• Floyd 後對每個城市統計 ≤ threshold 的個數，按規則選答案（最少、平手取較大索引）。

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int threshold) {
        const int INF = 1e9;
        vector<vector<int>> dist(n, vector<int>(n, INF));
        for (int i = 0; i < n; ++i) dist[i][i] = 0;
        for (auto &e: edges) {
            int u=e[0], v=e[1], w=e[2];
            dist[u][v] = min(dist[u][v], w);
            dist[v][u] = min(dist[v][u], w);
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i) if (dist[i][k] < INF)
                for (int j = 0; j < n; ++j) if (dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        int bestCity = -1, bestCnt = INT_MAX;
        for (int i = 0; i < n; ++i) {
            int cnt = 0;
            for (int j = 0; j < n; ++j)
                if (i != j && dist[i][j] <= threshold) cnt++;
            // 鄰居數更少，或平手取索引較大
            if (cnt < bestCnt || (cnt == bestCnt && i > bestCity)) {
                bestCnt = cnt; bestCity = i;
            }
        }
        return bestCity;
    }
};