Watch 10 video solutions for Minimum Cost of a Path With Special Roads, a medium level problem involving Array, Graph, Heap (Priority Queue). This walkthrough by Greg Hogg has 420,074 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 <= 105