P1113 [USACO02FEB] 雜務 - 洛谷
接上講，在做這道題的時候，是否遇到困難了？因為不僅僅是拓撲排序，還要求出最早完成時間。這引出了我們今天要討論的另一個話題：關鍵路徑。

關鍵路徑就是項目最短完成時間所經過的路徑。

求解關鍵路徑需要準備 2 個數(shù)組：

1. ve[i], 記錄從起點出發(fā)，最早什么時間能到達第 i 項任務。
2. vl[i], 不延遲的情況下，最晚什么時間必須到達任務 i。

其中，如果只求最短完成時間，例如開始那道題，ve 數(shù)組就足夠了；如果還要求關鍵路徑到達經過哪些節(jié)點，那就一定需要 vl 數(shù)組了。

我們還是用一道例題來說明這兩個數(shù)組的使用方法。設我們有 6 個點：

0→1 (3)
0→2 (2)
1→3 (2)
2→3 (1)
3→4 (4)
4→5 (2)

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

struct Edge {
    int to, w;
};

int main() {
    int n = 6;
    vector<vector<Edge>> adj(n);
    
    // 建圖
    auto add = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
    };
    
    add(0,1,3);
    add(0,2,2);
    add(1,3,2);
    add(2,3,1);
    add(3,4,4);
    add(4,5,2);
    
    // ---------- 1. 拓撲排序 ----------
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) {
        for (auto e : adj[u]) {
            indeg[e.to]++;
        }
    }
    
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) q.push(i);
    }
    
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto e : adj[u]) {
            if (--indeg[e.to] == 0) {
                q.push(e.to);
            }
        }
    }
    
    // ---------- 2. 求 ve ----------
    vector<int> ve(n, 0);
    
    for (int u : topo) {
        for (auto e : adj[u]) {
            ve[e.to] = max(ve[e.to], ve[u] + e.w);
        }
    }
    
    // 項目最短時間
    int maxTime = ve[topo.back()];
    
    // ---------- 3. 求 vl ----------
    vector<int> vl(n, maxTime);
    
    for (int i = n - 1; i >= 0; i--) {
        int u = topo[i];
        for (auto e : adj[u]) {
            vl[u] = min(vl[u], vl[e.to] - e.w);
        }
    }
    
    // ---------- 4. 輸出關鍵路徑 ----------
    cout << "Critical edges:\n";
    for (int u = 0; u < n; u++) {
        for (auto e : adj[u]) {
            if (ve[u] == vl[e.to] - e.w) {
                cout << u << " -> " << e.to << "\n";
            }
        }
    }
    
    cout << "Min project time = " << maxTime << endl;
    
    return 0;
}

我們現(xiàn)在該做的就是讀懂這段代碼，在參照這段代碼解決開頭的那道題目。