MediumRating 1757
3112. Minimum Time to Visit Disappearing Nodes
arraygraphheap-priority-queueshortest-path
解題說明
Minimum Time to Visit Disappearing Nodes
題目描述:給定一個無向加權圖和一個陣列 disappear,其中 disappear[i] 表示節點 i 在時間 disappear[i] 之後就會消失。求從節點 0 出發到達每個節點的最短時間,若到達時間 >= disappear[i] 則該節點不可達(回傳 -1)。
解題思路:這是帶有時間限制的 Dijkstra 最短路問題。使用標準 Dijkstra 演算法,但在鬆弛邊 (u, v, w) 時,需額外檢查到達 v 的時間 dist[u] + w 是否嚴格小於 disappear[v]。只有在節點未消失時才能經過或到達該節點。
C++ 解法
複雜度分析
時間複雜度:O((V + E) log V) — 標準 Dijkstra 的時間複雜度,V 為節點數,E 為邊數。
空間複雜度:O(V + E) — 鄰接表 O(E),距離陣列和優先佇列 O(V)。
虛擬碼
1. Build adjacency list from edges
2. Initialize dist[0] = 0, all others = INF
3. Push (0, node 0) to min-heap
4. While heap is not empty:
a. Pop (d, u); skip if d > dist[u]
b. For each neighbor (v, w) of u:
i. new_dist = d + w
ii. If new_dist < dist[v] AND new_dist < disappear[v]:
dist[v] = new_dist; push (new_dist, v)
5. Return dist array (replace INF with -1)其他解法
BFS + 0-1 BFS O(V + E):若邊權只有 0 和 1,可用 0-1 BFS(雙端佇列)替代 Dijkstra。但此題邊權任意,不適用。
Bellman-Ford O(V × E):可處理負權邊,但此題無負權且效率較差。Dijkstra 在此題是最佳選擇。
延伸思考
- 如果節點在某個時間區間內消失(而非永久消失),Dijkstra 需要如何修改?
- 如果起點不是節點 0 而是多個起點,如何修改為多源最短路?
- 如果邊也會在某個時間後消失,問題的複雜度會如何變化?