2662. Minimum Cost of a Path With Special Roads LeetCode Solution
In this guide, you will get 2662. Minimum Cost of a Path With Special Roads LeetCode Solution with the best time and space complexity. The solution to Minimum Cost of a Path With Special Roads problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimum Cost of a Path With Special Roads solution in C++
- Minimum Cost of a Path With Special Roads solution in Java
- Minimum Cost of a Path With Special Roads solution in Python
- Additional Resources
Problem Statement of Minimum Cost of a Path With Special Roads
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:
(1,1) to (1,2) with a cost of |1 – 1| + |2 – 1| = 1.
(1,2) to (3,3). Use specialRoads[0] with the cost 2.
(3,3) to (3,4) with a cost of |3 – 3| + |4 – 3| = 1.
(3,4) to (4,5). Use 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:
(1,1) to (1,2) with a cost of |1 – 1| + |2 – 1| = 1.
(1,2) to (7,4). Use specialRoads[1] with the cost 4.
(7,4) to (10,4) with a cost of |10 – 7| + |4 – 4| = 3.
Constraints:
start.length == target.length == 2
1 <= startX <= targetX <= 105
1 <= startY <= targetY <= 105
1 <= specialRoads.length <= 200
specialRoads[i].length == 5
startX <= x1i, x2i <= targetX
startY <= y1i, y2i <= targetY
1 <= costi <= 105
Complexity Analysis
- Time Complexity: O(n^2\log n)
- Space Complexity: O(n)
2662. Minimum Cost of a Path With Special Roads LeetCode Solution in C++
class Solution {
public:
int minimumCost(vector<int>& start, vector<int>& target,
vector<vector<int>>& specialRoads) {
return dijkstra(specialRoads, start[0], start[1], target[0], target[1]);
}
private:
int dijkstra(const vector<vector<int>>& specialRoads, int srcX, int srcY,
int dstX, int dstY) {
const int n = specialRoads.size();
// dist[i] := the minimum distance of (srcX, srcY) to
// specialRoads[i](x2, y2)
vector<int> dist(specialRoads.size(), INT_MAX);
using P = pair<int, int>; // (d, u), where u := the i-th specialRoads
priority_queue<P, vector<P>, greater<>> minHeap;
// (srcX, srcY) -> (x1, y1) to cost -> (x2, y2)
for (int u = 0; u < n; ++u) {
const int x1 = specialRoads[u][0];
const int y1 = specialRoads[u][1];
const int cost = specialRoads[u][4];
const int d = abs(x1 - srcX) + abs(y1 - srcY) + cost;
dist[u] = d;
minHeap.emplace(dist[u], u);
}
while (!minHeap.empty()) {
const auto [d, u] = minHeap.top();
minHeap.pop();
if (d > dist[u])
continue;
const int ux2 = specialRoads[u][2];
const int uy2 = specialRoads[u][3];
for (int v = 0; v < n; ++v) {
if (v == u)
continue;
const int vx1 = specialRoads[v][0];
const int vy1 = specialRoads[v][1];
const int vcost = specialRoads[v][4];
// (ux2, uy2) -> (vx1, vy1) to vcost -> (vx2, vy2)
const int newDist = d + abs(vx1 - ux2) + abs(vy1 - uy2) + vcost;
if (newDist < dist[v]) {
dist[v] = newDist;
minHeap.emplace(dist[v], v);
}
}
}
int ans = abs(dstX - srcX) + abs(dstY - srcY);
for (int u = 0; u < n; ++u) {
const int x2 = specialRoads[u][2];
const int y2 = specialRoads[u][3];
// (srcX, srcY) -> (x2, y2) -> (dstX, dstY).
ans = min(ans, dist[u] + abs(dstX - x2) + abs(dstY - y2));
}
return ans;
}
};
/* code provided by PROGIEZ */2662. Minimum Cost of a Path With Special Roads LeetCode Solution in Java
class Solution {
public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
return dijkstra(specialRoads, start[0], start[1], target[0], target[1]);
}
private int dijkstra(int[][] specialRoads, int srcX, int srcY, int dstX, int dstY) {
final int n = specialRoads.length;
// dist[i] := the minimum distance of (srcX, srcY) to
// specialRoads[i](x2, y2)
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
// (d, u), where u := the i-th specialRoads
Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));
// (srcX, srcY) -> (x1, y1) to cost -> (x2, y2)
for (int u = 0; u < n; ++u) {
final int x1 = specialRoads[u][0];
final int y1 = specialRoads[u][1];
final int cost = specialRoads[u][4];
final int d = Math.abs(x1 - srcX) + Math.abs(y1 - srcY) + cost;
dist[u] = d;
minHeap.offer(new Pair<>(dist[u], u));
}
while (!minHeap.isEmpty()) {
final int d = minHeap.peek().getKey();
final int u = minHeap.poll().getValue();
if (d > dist[u])
continue;
final int ux2 = specialRoads[u][2];
final int uy2 = specialRoads[u][3];
for (int v = 0; v < n; ++v) {
if (v == u)
continue;
final int vx1 = specialRoads[v][0];
final int vy1 = specialRoads[v][1];
final int vcost = specialRoads[v][4];
// (ux2, uy2) -> (vx1, vy1) to vcost -> (vx2, vy2)
final int newDist = d + Math.abs(vx1 - ux2) + Math.abs(vy1 - uy2) + vcost;
if (newDist < dist[v]) {
dist[v] = newDist;
minHeap.offer(new Pair<>(dist[v], v));
}
}
}
int ans = Math.abs(dstX - srcX) + Math.abs(dstY - srcY);
for (int u = 0; u < n; ++u) {
final int x2 = specialRoads[u][2];
final int y2 = specialRoads[u][3];
// (srcX, srcY) -> (x2, y2) -> (dstX, dstY).
ans = Math.min(ans, dist[u] + Math.abs(dstX - x2) + Math.abs(dstY - y2));
}
return ans;
}
}
// code provided by PROGIEZ2662. Minimum Cost of a Path With Special Roads LeetCode Solution in Python
class Solution:
def minimumCost(
self,
start: list[int],
target: list[int],
specialRoads: list[list[int]],
) -> int:
return self.dijkstra(specialRoads, *start, *target)
def dijkstra(
self,
specialRoads: list[list[int]],
srcX: int,
srcY: int,
dstX: int,
dstY: int,
) -> int:
n = len(specialRoads)
# dist[i] := the minimum distance of (srcX, srcY) to specialRoads[i](x2, y2)
dist = [math.inf] * n
minHeap = [] # (d, u), where u := the i-th specialRoads
# (srcX, srcY) -> (x1, y1) to cost -> (x2, y2)
for u, (x1, y1, _, _, cost) in enumerate(specialRoads):
d = abs(x1 - srcX) + abs(y1 - srcY) + cost
dist[u] = d
heapq.heappush(minHeap, (dist[u], u))
while minHeap:
d, u = heapq.heappop(minHeap)
if d > dist[u]:
continue
_, _, ux2, uy2, _ = specialRoads[u]
for v in range(n):
if v == u:
continue
vx1, vy1, _, _, vcost = specialRoads[v]
# (ux2, uy2) -> (vx1, vy1) to vcost -> (vx2, vy2)
newDist = d + abs(vx1 - ux2) + abs(vy1 - uy2) + vcost
if newDist < dist[v]:
dist[v] = newDist
heapq.heappush(minHeap, (dist[v], v))
ans = abs(dstX - srcX) + abs(dstY - srcY)
for u in range(n):
_, _, x2, y2, _ = specialRoads[u]
# (srcX, srcY) -> (x2, y2) -> (dstX, dstY).
ans = min(ans, dist[u] + abs(dstX - x2) + abs(dstY - y2))
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.