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 <= 105In #2662 Minimum Cost of a Path With Special Roads, you need to move from a start point to a target point on a 2D grid where normal movement costs the Manhattan distance. However, certain special roads allow you to travel between two coordinates at a potentially lower fixed cost.
The key idea is to treat important coordinates (start point, target point, and special road endpoints) as nodes in a graph. Moving normally between two nodes costs their Manhattan distance, while taking a special road uses its provided cost. With this graph representation, the task becomes a classic shortest path problem.
A common approach is to apply Dijkstra's algorithm with a priority queue. At each step, you expand the current minimum-cost position and evaluate whether using special roads or normal movement reduces the total distance. Carefully considering transitions between road endpoints ensures all beneficial shortcuts are explored.
This approach efficiently finds the minimum cost while avoiding brute-force exploration of the infinite grid.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dijkstra with Priority Queue over special road endpoints | O(n^2 log n) | O(n) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
It can be proven that it is optimal to go only to the positions that are either the start or the end of a special road or the target position.
Consider all positions given to you as nodes in a graph, and the edges of the graph are the special roads.
Now the problem is equivalent to finding the shortest path in a directed graph.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The problem involves finding the minimum travel cost between nodes with non-negative edge weights. Since both Manhattan distances and special road costs are non-negative, Dijkstra's algorithm is a natural and efficient choice.
Problems involving shortest path algorithms, coordinate graphs, and priority queues are common in FAANG interviews. Variations of this problem test a candidate's ability to model real-world scenarios as graph problems and apply Dijkstra effectively.
A priority queue (min-heap) is essential for efficiently implementing Dijkstra's algorithm. It allows you to repeatedly process the node with the current minimum travel cost while exploring beneficial special roads.
The optimal approach models key coordinates as graph nodes and applies Dijkstra's shortest path algorithm. Each move either uses Manhattan distance or a special road cost. A priority queue helps always expand the lowest-cost state first.