MediumRating 2154

2662. Minimum Cost of a Path With Special Roads

arraygraphheap-priority-queueshortest-path

解題說明

Minimum Cost of a Path With Special Roads

題目描述：在二維平面上，從起點 (startX, startY) 到終點 (targetX, targetY)，正常移動的代價是曼哈頓距離。另外有一些特殊道路，每條特殊道路有起點 (x1, y1)、終點 (x2, y2) 和代價 cost（可能比曼哈頓距離便宜）。求最小移動代價。

解題思路：將起點、終點和所有特殊道路的端點都視為圖的節點。任意兩個節點之間都可以用曼哈頓距離直接到達。特殊道路提供了一條可能更便宜的邊。

建圖後使用 Dijkstra 求最短路。節點數最多為 2 + 2 * |specialRoads|（起點、終點加上每條特殊路的兩端點），規模不大。

注意：可以只使用特殊道路的終點加上起點和終點作為關鍵節點（因為從任何點到特殊道路起點走曼哈頓距離，然後走特殊道路到終點）。

C++ 解法

複雜度分析

時間複雜度：O(m^2 log m) — 其中 m 為特殊道路數量。每個節點最多鬆弛 m 條邊，共 O(m) 個節點

空間複雜度：O(m) — 儲存節點的最短距離和優先佇列

虛擬碼

1. Define Manhattan distance function
2. Initialize Dijkstra from start point with distance 0
3. While priority queue is not empty:
   a. Pop node (x, y) with minimum distance d
   b. If already visited with shorter distance, skip
   c. If (x, y) is target, return d
   d. Try going directly to target: cost = d + manhattan(x, y, target)
   e. For each special road (x1, y1, x2, y2, cost):
      - Try: cost = d + manhattan(x, y, x1, y1) + road_cost
      - If shorter, push (x2, y2) with new cost
4. Return distance to target

其他解法

Floyd-Warshall 法：建立所有節點（起點、終點、特殊路端點）之間的距離矩陣，用 Floyd-Warshall 求全源最短路。時間 O(m^3)，空間 O(m^2)。在節點數少時可行但通常比 Dijkstra 慢。
SPFA（Bellman-Ford 佇列優化）法：用佇列代替優先佇列，適合有負權邊的情況。本題所有邊權為正，Dijkstra 更高效。

延伸思考

如果特殊道路是雙向的，如何修改建圖？
如果可以使用每條特殊道路最多 k 次，如何建模？
如果座標範圍很大但需要輸出完整路徑（而非只是代價），如何追蹤路徑？

Minimum Cost of a Path With Special Roads — CaffeCode