SDOI 2010 大陸爭霸：Dijkstra 變體求城市最早可進入時間

問題建模

有向圖，每條邊有長度。城市 x 有兩個時間：d1[x] 到達時間，d2[x] 可進入時間（需所有保護城市均可進入）。真實進入時間 = max(d1[x], d2[x])。每次取真實時間最小的城市擴展。

關鍵數據結構

• d1[x]：最短路到達時間
• d2[x]：保護城市中最晚可進入時間
• deg[x]：尚未就緒的保護城市數
• 優先隊列 (time, city)，按 max(d1, d2) 排序

算法流程

1. 初始：d1[1]=d2[1]=0，其他 INF，deg[x] 為入度
2. 堆中取出時間最小城市 u
3. 鬆弛出邊：d1[v] = min(d1[v], max(d1[u],d2[u]) + w)
4. 更新保護城市：d2[prot] = max(d2[prot], max(d1[u],d2[u]))，deg[prot]--
5. 若 deg[prot]==0 且未訪問，入堆

複雜度

O((n+m) log n)，n ≤ 80000，m 為邊數，完全可行。

代碼框架

priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
q.push({0,1});
while (!q.empty()) {
    auto [t,u] = q.top(); q.pop();
    if (vis[u]) continue;
    vis[u]=1;
    ll real = max(d1[u], d2[u]);
    // 鬆弛邊、更新保護城市...
}

核心洞察

將「保護關係」建模為反向依賴，結合 Dijkstra 的「已確定最短路不再改變」性質，巧妙解決雙時間約束。