題目描述:給定一個 n 個節點的有向加權圖,每條邊 (u, v, w) 表示從 u 到 v 需要 w 時間。但有一個特殊限制:到達某節點後,需要等待至少該節點的等待時間才能繼續出發。求從節點 0 到節點 n-1 的最短時間。若無法到達,回傳 -1。
解題思路:這是 Dijkstra 最短路徑的變體。使用最小堆(priority queue)維護 (當前時間, 節點) 對。對於每個從堆中取出的節點 u,遍歷其所有出邊 (u, v, w),計算到達 v 的時間。若 v 有等待時間限制,需要取 max(arrival_time, wait_time[v]) 再加上邊權。標準 Dijkstra 確保每個節點第一次被取出時即為最短時間。
時間複雜度:O((V + E) log V) — 標準 Dijkstra,V 為節點數,E 為邊數。
空間複雜度:O(V + E) — 鄰接表和距離陣列。
1. Build adjacency list from edges
2. Initialize dist[] = infinity, dist[0] = 0
3. Push (0, node 0) into min-heap
4. While heap is not empty:
a. Pop (d, u) with smallest d
b. If d > dist[u]: skip (outdated entry)
c. If u == n-1: return d
d. For each neighbor (v, w) of u:
- newDist = d + w
- If newDist < dist[v]: update dist[v], push (newDist, v)
5. Return -1 if n-1 unreachableBellman-Ford O(V * E):可以處理負權邊的最短路演算法。本題邊權為正,Dijkstra 更高效,但 Bellman-Ford 實作更簡單。
SPFA (Shortest Path Faster Algorithm):Bellman-Ford 的佇列優化版本,平均效能接近 Dijkstra,但最差情況仍為 O(V * E)。