BZOJ SDOI 2010 大陸爭霸：帶結界約束的最短路——拓撲序 + Dijkstra 優化 O((N+M) log N)

問題建模

有向圖 N 點 M 邊，邊權 w。點 1 為起點，點 N 為終點（大神殿）。每個點 i 有 L_i 個「結界發生器」分佈在其他點，必須**先摧毀所有發生器**才能進入該點。摧毀發生器或大神殿需派遣一個自爆機器人（到達即引爆）。機器人無限，求摧毀大神殿的最短時間。

關鍵轉化

• 「摧毀發生器」本質是**先到達發生器所在點**。
• 進入點 v 的前置條件：所有維持 v 結界的發生器點 u 已被到達（摧毀）。
• 這構成一個**依賴圖**：u → v 表示 u 是 v 的發生器，必須先「完成」 u。
• 原圖邊 u → v 表示機器人可從 u 移動到 v，耗時 w。

核心洞察：雙重圖融合

定義 f[v] = 到達並完成點 v（摧毀其發生器/神殿）的最早時間。
則 f[v] = max( 到達v的最早時間, max_{u∈發生器(v)} f[u] )。
其中「到達v的最早時間」取決於圖邊傳播：d[v] = min_{u→v} (f[u] + w)。
這是一個**動態規劃在圖上**的系統，可用**優先隊列（Dijkstra 風格）**求解。

算法流程

1. 構建**依賴圖**反向邊：對每個發生器 u 維護 v 的列表 revDep[u]，以及入度 deg[v] = 發生器數量。
2. 初始化 d[1]=f[1]=0，其餘 INF。入度為 0 的點入優先隊列（按 f 值小根堆）。
3. 循環取堆頂 u（當前 f[u] 最小且已確定）：
   • 對原圖出邊 u → v：d[v] = min(d[v], f[u] + w)。若 d[v] 更新且 d[v] ≥ f[v]（滿足所有發生器），則 f[v] = d[v] 入堆。
   • 對依賴反邊 u → v（u 是 v 的發生器）：deg[v]--，f[v] = max(f[v], f[u])。若 deg[v]==0 且 d[v] ≤ f[v]，則 f[v] 已確定入堆。
4. 最終 f[N] 即答案。

代碼實現（C++，優先隊列優化）

#include 
using namespace std;
using ll = long long;
const ll INF = 4e18;

struct Edge { int to; ll w; };
struct DepEdge { int to; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector> g(n+1);
    for (int i=0;i>u>>v>>w;
        if (u!=v) g[u].push_back({v,w});
    }
    vector> revDep(n+1);
    vector deg(n+1);
    for (int v=1; v<=n; ++v) {
        int k; cin>>k; deg[v]=k;
        for (int i=0;i>u;
            revDep[u].push_back(v); // u 是 v 的發生器
        }
    }
    vector d(n+1, INF), f(n+1, INF);
    d[1]=f[1]=0;
    using pli = pair;
    priority_queue, greater> pq;
    pq.push({0,1});
    vector inQueue(n+1, 0);
    inQueue[1]=1;
    while (!pq.empty()) {
        auto [fu, u] = pq.top(); pq.pop();
        inQueue[u]=0;
        if (fu != f[u]) continue; // 過時條目
        // 1. 原圖邊鬆弛
        for (auto& e : g[u]) {
            int v = e.to;
            if (d[v] > fu + e.w) {
                d[v] = fu + e.w;
                if (d[v] >= f[v] && !inQueue[v]) { // 所有發生器已滿足
                    f[v] = d[v];
                    pq.push({f[v], v});
                    inQueue[v]=1;
                }
            }
        }
        // 2. 依賴反邊更新
        for (int v : revDep[u]) {
            f[v] = max(f[v], fu);
            if (--deg[v] == 0) { // 所有發生器完成
                if (d[v] <= f[v] && !inQueue[v]) {
                    // f[v] 已是 max(發生器完成時間), d[v] 已是最早到達時間
                    // 實際完成時間 = max(f[v], d[v]) = f[v] (因d[v]<=f[v])
                    pq.push({f[v], v});
                    inQueue[v]=1;
                }
            }
        }
    }
    cout << f[n] << '\n';
    return 0;
}

正確性論證

• 類似 Dijkstra，每次取出的 f[u] 是當前未確定點中的最小值，且不再更新（因所有可能減小它的路徑/依賴已處理）。
• f[v] = max(最早到達時間, 所有發生器完成時間) 的定義在算法中通過 d[v]（最早到達）與 deg[v]（發生器計數）共同維護。
• 當 deg[v]==0 且 d[v] ≤ f[v] 時，f[v] 確定為 max(f[v], d[v]) = f[v]；若 d[v] > f[v]，則需等待原圖邊鬆弛更新 d[v] 後再入堆。

複雜度

• 時間：O((N+M) log N)，每條邊/依賴最多鬆弛一次，堆操作 log N。
• 空間：O(N+M)。
• 滿足 N≤3000, M≤70000 限制。