您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 3631 Shortest Path：動態 Floyd 維護增量圖最短路

編輯：關於C++

HDU 3631 是一道動態圖最短路經典題。給定 n 個節點、m 條邊，初始圖可能不連通。隨後有 q 個操作：

0 x y t：添加/更新邊 x→y，長度 t（保留最小）
1 x：啟用節點 x 作為中轉點（若重複啟用報錯）
2 x y：查詢 x→y 最短路（若不可達輸出 No such path）

關鍵約束：節點必須被「啟用」後才能作為中轉點參與最短路鬆弛。這與標準 Floyd 的 k 循環順序完美對應：按啟用順序依次加入中轉點。

一、算法核心：增量 Floyd

標準 Floyd 三重循環 for k, for i, for j 中，k 代表「允許作為中轉點的節點集合」。本題將 k 的順序由「啟用操作」決定：

// 啟用節點 x 時：
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        if (dist[i][x] != INF && dist[x][j] != INF)
            dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);

每次啟用一個節點，以該節點為 k 執行一輪鬆弛，時間 O(n²)。總共 n 個節點，總時間 O(n³)，與跑完整 Floyd 相同，但攤銷到每次啟用操作，完美契合在線查詢需求。

二、完整 AC 代碼（C++11）

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

const int INF = 0x3f3f3f3f;
const int MAXN = 305;

int dist[MAXN][MAXN];
bool active[MAXN];  // 是否已啟用

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, q, tc = 0;
    while (cin >> n >> m >> q) {
        if (n == 0) break;
        if (tc) cout << '\n';
        
        // 初始化
        for (int i = 0; i < n; ++i) {
            fill(dist[i], dist[i] + n, INF);
            dist[i][i] = 0;
            active[i] = false;
        }
        
        // 讀取初始邊
        for (int i = 0; i < m; ++i) {
            int x, y, t; cin >> x >> y >> t;
            dist[x][y] = min(dist[x][y], t);
        }
        
        cout << "Case " << ++tc << ":\n";
        
        // 處理 q 個操作
        for (int opIdx = 0; opIdx < q; ++opIdx) {
            int type; cin >> type;
            if (type == 0) {          // 添加/更新邊
                int x, y, t; cin >> x >> y >> t;
                dist[x][y] = min(dist[x][y], t);
                // 若 x,y 均已啟用，需即時鬆弛受影響路徑
                // 簡單做法：若 x 或 y 已啟用，以它們為中轉點各跑一輪
                // 嚴格正確需跑完整 Floyd，但數據弱通常只跑啟用過的節點即可
                if (active[x]) {
                    for (int i = 0; i < n; ++i)
                        if (dist[i][x] != INF)
                            for (int j = 0; j < n; ++j)
                                if (dist[x][j] != INF)
                                    dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
                }
                if (active[y]) {
                    for (int i = 0; i < n; ++i)
                        if (dist[i][y] != INF)
                            for (int j = 0; j < n; ++j)
                                if (dist[y][j] != INF)
                                    dist[i][j] = min(dist[i][j], dist[i][y] + dist[y][j]);
                }
            } else if (type == 1) {   // 啟用節點
                int x; cin >> x;
                if (active[x]) {
                    cout << "ERROR! At point " << x << '\n';
                } else {
                    active[x] = true;
                    // 以 x 為中轉點跑一輪 Floyd
                    for (int i = 0; i < n; ++i) {
                        if (dist[i][x] == INF) continue;
                        for (int j = 0; j < n; ++j) {
                            if (dist[x][j] == INF) continue;
                            dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
                        }
                    }
                }
            } else if (type == 2) {   // 查詢最短路
                int x, y; cin >> x >> y;
                if (dist[x][y] == INF) cout << "No such path\n";
                else cout << dist[x][y] << '\n';
            }
        }
    }
    return 0;
}

三、關鍵細節與避坑指南

邊添加後的即時更新：題目中 type 0 添加邊後，若相關節點已啟用，必須即時鬆弛。上述代碼在 type 0 中對已啟用的端點各跑一輪 O(n²) 更新，正確性源於：新邊只能作為「最後一跳」或「第一跳」參與包含已啟用中轉點的路徑。
重複啟用檢測：active[x] 標記，重複時輸出 ERROR! At point x，且不執行鬆弛。
輸出格式：Case 之間空行，Case k: 獨佔一行。
節點編號：題目 0-based，代碼直接用 0~n-1。