MediumRating 1854
3650. Minimum Cost Path with Edge Reversals
graphheap-priority-queueshortest-path
解題說明
Minimum Cost Path with Edge Reversals
題目描述：給定一個有向加權圖，需要從節點 0 走到節點 n-1。可以沿正向走一條邊（成本為該邊的權值），也可以反向走一條邊（成本為反轉該邊的額外費用）。求從 0 到 n-1 的最小總成本。
解題思路：將問題轉化為標準最短路。對於每條有向邊 (u, v, w)，在圖中加入兩條邊：正向 (u → v) 成本 w，以及反向 (v → u) 成本為反轉費用。然後在這個新圖上跑 Dijkstra 求從 0 到 n-1 的最短路徑。常見的建模是：正向邊成本為 0（沿著原方向走不額外花費，或者花費 w），反向邊成本為 1（或特定的反轉費用）。
C++ 解法
複雜度分析
時間複雜度：O((V + E) log V) — Dijkstra 在擴展圖上的標準複雜度。邊數加倍但不影響漸進複雜度。
空間複雜度：O(V + E) — 擴展後的鄰接表和距離陣列。
虛擬碼
1. Build expanded graph: - For each directed edge (u, v, w): add forward edge u->v with cost w - Add reverse edge v->u with reverse cost 2. Run Dijkstra from node 0 3. Return dist[n-1] or -1 if unreachable
其他解法
0-1 BFS：若正向成本為 0、反向成本為 1（邊反轉的特殊情況），可以用 0-1 BFS（deque-based BFS），時間複雜度 O(V + E)，比 Dijkstra 更快。
Bellman-Ford O(V * E)：通用最短路算法，可處理負權邊。本題邊權非負，Dijkstra 更適合。
延伸思考
- 如果最多只能反轉 k 條邊，該如何修改演算法？（提示：擴展狀態為 (node, reversals_used)）
- 若邊的反轉成本為 0（免費反轉），問題是否等價於無向圖最短路？
- 如果圖中有多個目的地，需要找到成本最小的那個，如何修改？