MediumRating 1845

3604. Minimum Time to Reach Destination in Directed Graph

graphheap-priority-queueshortest-path

解題說明

Minimum Time to Reach Destination in Directed Graph

題目描述：給定一個 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 確保每個節點第一次被取出時即為最短時間。

C++ 解法

複雜度分析

時間複雜度：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 unreachable

其他解法

Bellman-Ford O(V * E)：可以處理負權邊的最短路演算法。本題邊權為正，Dijkstra 更高效，但 Bellman-Ford 實作更簡單。

SPFA (Shortest Path Faster Algorithm)：Bellman-Ford 的佇列優化版本，平均效能接近 Dijkstra，但最差情況仍為 O(V * E)。

延伸思考

如果某些邊的通行時間會隨時間變化（時間依賴的圖），該如何修改 Dijkstra？
如果需要同時找出最短路徑的具體路線（而非僅回傳距離），如何記錄前驅節點？
若圖是無向的且可能有負權邊，應使用什麼演算法？

Minimum Time to Reach Destination in Directed Graph — CaffeCode