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 而是多個起點，如何修改為多源最短路？
- 如果邊也會在某個時間後消失，問題的複雜度會如何變化？