2662. Minimum Cost of a Path With Special Roads

解題說明

C++ 解法

複雜度分析

虛擬碼

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

其他解法

延伸思考