題目描述:給定一個無向加權圖和一個陣列 disappear,其中 disappear[i] 表示節點 i 在時間 disappear[i] 之後就會消失。求從節點 0 出發到達每個節點的最短時間,若到達時間 >= disappear[i] 則該節點不可達(回傳 -1)。
解題思路:這是帶有時間限制的 Dijkstra 最短路問題。使用標準 Dijkstra 演算法,但在鬆弛邊 (u, v, w) 時,需額外檢查到達 v 的時間 dist[u] + w 是否嚴格小於 disappear[v]。只有在節點未消失時才能經過或到達該節點。
時間複雜度: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 在此題是最佳選擇。