HardRating 1998

3620. Network Recovery Pathways

arraybinary-searchdynamic-programminggraphtopological-sortheap-priority-queueshortest-path

解題說明

Network Recovery Pathways

題目描述：給定一個有向加權圖，代表一個網路。每條邊有一個「修復時間」。網路從節點 0 開始修復，只有當所有通往某節點的前置路徑都修復完畢後，該節點才算修復完成。求修復節點 n-1 的最短時間。若無法修復，回傳 -1。

解題思路：這是一個結合了最長路與最短路概念的問題。到達某節點的修復時間取決於所有入邊的最大修復完成時間（因為要等所有前置完成）。因此，對每個節點，其修復時間為：max(所有入邊的 source 修復時間 + 邊的修復時間) 或者 min(所有可能路徑的 max 值)。

可以用修改版的 Dijkstra：使用最小堆，對每個節點追蹤到達它的「最大路徑時間」。但更精確的方法是使用拓撲排序（若為 DAG）或 Dijkstra 的變體，根據問題的具體約束決定。

C++ 解法

複雜度分析

時間複雜度：O((V + E) log V) — Dijkstra 最短路徑的標準複雜度。

空間複雜度：O(V + E) — 鄰接表和距離陣列。

虛擬碼

1. Build adjacency list from directed edges
2. Initialize dist[] = infinity, dist[0] = 0
3. Push (0, node 0) into min-heap
4. Dijkstra relaxation:
   a. Pop (d, u) with smallest d
   b. Skip if d > dist[u]
   c. For each edge (u, v, w): if d + w < dist[v], update and push
5. Return dist[n-1] or -1 if unreachable

其他解法

拓撲排序 + DP（若為 DAG）O(V + E)：若圖保證無環，可用拓撲排序後線性計算每個節點的修復時間。比 Dijkstra 更快但僅適用於 DAG。

Bellman-Ford O(V * E)：若存在特殊邊權結構（如可能需要考慮負權），Bellman-Ford 可作為替代。但本題邊權為正，Dijkstra 更優。

延伸思考

如果修復可以並行進行（多條路徑同時修復），如何建模為最大流問題？
若每個節點有修復容量限制（同時只能處理一條入邊的修復），如何調整？
若需要找出修復路徑上的瓶頸邊（修復時間最長的邊），如何一併回傳？

Network Recovery Pathways — CaffeCode