Watch 9 video solutions for Minimum Cost of a Path With Special Roads, a medium level problem involving Array, Graph, Heap (Priority Queue). This walkthrough by Hua Hua has 3,113 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY).
The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.
There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1i, y1i, x2i, y2i, costi] indicates that the ith special road goes in one direction from (x1i, y1i) to (x2i, y2i) with a cost equal to costi. You can use each special road any number of times.
Return the minimum cost required to go from (startX, startY) to (targetX, targetY).
Example 1:
Input: start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]
Output: 5
Explanation:
specialRoads[0] with the cost 2.specialRoads[1] with the cost 1.So the total cost is 1 + 2 + 1 + 1 = 5.
Example 2:
Input: start = [3,2], target = [5,7], specialRoads = [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]
Output: 7
Explanation:
It is optimal not to use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.
Note that the specialRoads[0] is directed from (5,7) to (3,2).
Example 3:
Input: start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]
Output: 8
Explanation:
specialRoads[1] with the cost 4.
Constraints:
start.length == target.length == 21 <= startX <= targetX <= 1051 <= startY <= targetY <= 1051 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1i, x2i <= targetXstartY <= y1i, y2i <= targetY1 <= costi <= 105Problem Overview: You start at a coordinate on a 2D grid and need the minimum cost to reach a target. Moving normally costs the Manhattan distance between points, but some special roads let you travel between two coordinates with a custom cost. The goal is to combine normal movement and special roads to minimize total travel cost.
Approach 1: Dijkstra's Algorithm (O(n log n) time, O(n) space)
Treat the problem as a graph shortest path problem. Each relevant coordinate becomes a node: the start position and the start/end points of every special road. From any node, you can move to another coordinate using Manhattan distance, or take a special road with its given cost. Use Dijkstra’s algorithm with a heap (priority queue) to always expand the currently cheapest reachable position. The key insight is that you do not need to explore every grid cell—only the special road endpoints. Each relaxation step compares the cost of normal movement versus the cost of using a special road. This approach efficiently computes the optimal route while avoiding the huge state space of the entire grid.
Approach 2: Bellman-Ford Algorithm (O(n^2) time, O(n) space)
Model the same coordinate set as a weighted graph and run the shortest path relaxation process using Bellman-Ford. Initialize the distance to each special road endpoint as the Manhattan distance from the start. Then repeatedly relax all edges: traveling normally between endpoints or taking a special road edge. After enough iterations, the distances converge to the minimum possible costs. Bellman-Ford works well because edge weights can be arbitrary but remain non-negative in this problem. The downside is performance—every iteration scans all edges, which increases runtime compared to Dijkstra’s priority-driven exploration.
Recommended for interviews: Dijkstra’s algorithm is the expected solution. It shows you recognize the hidden graph structure and can combine Manhattan distance with weighted edges efficiently. Bellman-Ford demonstrates understanding of general shortest-path relaxation but is rarely chosen unless negative edges exist. Interviewers usually want to see the priority queue–based optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm with Priority Queue | O(n log n) | O(n) | Best general solution for non-negative weighted graphs and optimal interview answer |
| Bellman-Ford Algorithm | O(n^2) | O(n) | Useful when implementing generic edge relaxation or when negative edges could exist |