HardRating 2202
2045. Second Minimum Time to Reach Destination
breadth-first-searchgraphshortest-path
解題說明
Second Minimum Time to Reach Destination
題目描述： 給定一個無向圖，n 個節點、m 條邊，每條邊通過時間為 time。每個節點有紅綠燈，週期為 change。綠燈時可通過，紅燈時需等待到下一次綠燈。求從節點 1 到節點 n 的嚴格第二短時間。
解題思路： 使用修改版的 BFS，對每個節點記錄到達的最短時間和嚴格第二短時間。
- 對每個節點維護兩個距離值：dist1（最短）和 dist2（嚴格第二短）。
- BFS 擴展時，若當前時間在紅燈期（
(curTime / change) % 2 == 1），需等待到下一個綠燈週期。 - 等待後加上 time 得到到達鄰居的時間 newTime。
- 若 newTime < dist1[neighbor]，更新 dist1 並入隊。
- 若 newTime > dist1[neighbor] 且 newTime < dist2[neighbor]，更新 dist2 並入隊。
- 最終 dist2[n] 即為答案。
因為邊權相同且等待時間確定，BFS 可以保證按時間順序探索。
C++ 解法
複雜度分析
時間複雜度：O(n + m) — 每個節點最多被處理兩次（最短和第二短），每條邊最多被考慮常數次。
空間複雜度：O(n + m) — 鄰接表 O(m)，距離陣列和佇列 O(n)。
虛擬碼
1. Build adjacency list from edges.
2. Initialize dist1[1..n] = INF, dist2[1..n] = INF, dist1[1] = 0.
3. BFS queue starts with (node=1, time=0).
4. For each (node, curTime) from queue:
a. If (curTime / change) is odd, wait until next green: waitTime = change - (curTime % change).
b. newTime = curTime + waitTime + time.
c. For each neighbor of node:
- If newTime < dist1[neighbor]: update dist2, dist1, enqueue.
- Else if dist1[neighbor] < newTime < dist2[neighbor]: update dist2, enqueue.
5. Return dist2[n].其他解法
-
Dijkstra 變體：使用優先佇列（min-heap）替代普通佇列。對於此題邊權相同的情況效率相近，但在邊權不同的擴展問題中更通用。時間複雜度 O((n + m) log n)。
-
列舉路徑長度：先用 BFS 求出最短路徑長度 d，則第二短路徑要嘛是 d+2（走一條多餘的邊再返回），要嘛是另一條不同的路。計算這兩種情況的實際時間並取較小值。
延伸思考
- 若不同邊的通過時間不同，該如何修改演算法？
- 若紅綠燈不是全域同步，而是每個節點有不同的週期和初始相位，解法需要怎麼調整？
- 如何擴展此方法求第 K 短時間？空間和時間複雜度會如何變化？