Minimum Cost of a Path With Special Roads
MedPrompt
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 == 21 <= startX <= targetX <= 1051 <= startY <= targetY <= 1051 <= specialRoads.length <= 200specialRoads[i].length == 5startX <= x1i, x2i <= targetXstartY <= y1i, y2i <= targetY1 <= costi <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach models the problem as a classic shortest path problem on a graph. The nodes of the graph are the start point, target point, and all the start and end points of the special roads. The edges represent the cost of travel between these points. By constructing this graph explicitly and then running Dijkstra's algorithm, we can find the minimum cost from the start to the target.
Algorithm
- Collect all unique key points:
start,target, and all start/end points ofspecialRoads. Let there beMsuch points. - Create a mapping from each point to an index from
0toM-1. - Build an adjacency list representing a complete graph. For every pair of points
uandv, the edge weight is the minimum of the Manhattan distance and the cost of a special road if one exists between them. - This results in a graph with
Mnodes andO(M^2)edges. - Apply Dijkstra's algorithm on this graph, starting from the
startnode's index. - The result is the computed shortest distance to the
targetnode's index.
Walkthrough
First, we identify all critical points in the 2D space. These are the start point, the target point, and all start and end coordinates of the specialRoads. Let's say there are M unique such points. These points will be the vertices of our graph.
We then construct a complete directed graph where the weight of the edge from any point u to any point v is initially the Manhattan distance |u.x - v.x| + |u.y - v.y|. The special roads introduce alternative, potentially cheaper, paths. For each special road from a point u to a point v with cost c, we update the weight of the directed edge from u to v to be the minimum of its current weight and c.
After constructing this graph with M vertices and O(M^2) edges, the problem is reduced to finding the shortest path from the start node to the target node. Dijkstra's algorithm is perfectly suited for this since all edge weights are non-negative. The final answer is the shortest distance computed for the target node.
import java.util.*; class Solution { private long manhattanDist(int[] p1, int[] p2) { return Math.abs((long)p1[0] - p2[0]) + Math.abs((long)p1[1] - p2[1]); } public int minimumCost(int[] start, int[] target, int[][] specialRoads) { List<int[]> points = new ArrayList<>(); Map<Long, Integer> pointToIndex = new HashMap<>(); java.util.function.Function<int[], Integer> addPoint = (p) -> { long key = (long)p[0] * 100001L + p[1]; if (!pointToIndex.containsKey(key)) { pointToIndex.put(key, points.size()); points.add(p); } return pointToIndex.get(key); }; addPoint.apply(start); addPoint.apply(target); for (int[] road : specialRoads) { addPoint.apply(new int[]{road[0], road[1]}); addPoint.apply(new int[]{road[2], road[3]}); } int n = points.size(); List<List<long[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } Map<Long, Long> specialEdgeCosts = new HashMap<>(); for (int[] road : specialRoads) { long uKey = (long)road[0] * 100001L + road[1]; long vKey = (long)road[2] * 100001L + road[3]; long edgeKey = (uKey << 32) | vKey; specialEdgeCosts.put(edgeKey, Math.min(specialEdgeCosts.getOrDefault(edgeKey, Long.MAX_VALUE), (long)road[4])); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; long p1Key = (long)points.get(i)[0] * 100001L + points.get(i)[1]; long p2Key = (long)points.get(j)[0] * 100001L + points.get(j)[1]; long edgeKey = (p1Key << 32) | p2Key; long cost = manhattanDist(points.get(i), points.get(j)); cost = Math.min(cost, specialEdgeCosts.getOrDefault(edgeKey, Long.MAX_VALUE)); adj.get(i).add(new long[]{j, cost}); } } long[] dist = new long[n]; Arrays.fill(dist, Long.MAX_VALUE); int startIdx = addPoint.apply(start); int targetIdx = addPoint.apply(target); dist[startIdx] = 0; PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); pq.offer(new long[]{0, startIdx}); while (!pq.isEmpty()) { long[] current = pq.poll(); long d = current[0]; int u = (int) current[1]; if (d > dist[u]) continue; if (u == targetIdx) return (int) d; for (long[] edge : adj.get(u)) { int v = (int) edge[0]; long weight = edge[1]; if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.offer(new long[]{dist[v], v}); } } } return (int) dist[targetIdx]; }}Complexity
Time
O(M^2 log M), where M is the number of unique key points (at most 2N+2, where N is the number of special roads). Building the graph takes O(M^2) and Dijkstra's algorithm on a dense graph with a priority queue takes O(E log M) = O(M^2 log M).
Space
O(M^2), where M is the number of unique key points (at most 2N+2). This is for storing the adjacency list of the dense graph.
Trade-offs
Pros
Conceptually straightforward application of a standard algorithm.
Guaranteed to find the optimal solution.
Cons
Higher space complexity due to storing a dense graph.
Higher time complexity compared to the optimized approach.
Implementation can be more complex due to the need to correctly merge Manhattan distance costs and special road costs into a single graph structure.
This is a more refined application of Dijkstra's algorithm that leverages the specific structure of the problem. Instead of building a graph of all key points, we focus on finding the minimum cost to reach only the destination points of the special roads. This is because any optimal path will consist of segments of normal travel connecting the start, target, and special road endpoints. This approach efficiently calculates the costs to these crucial 'junction' points.
Algorithm
- Initialize the minimum cost to be the direct Manhattan distance from
starttotarget. - Use a priority queue for Dijkstra's algorithm to find the minimum cost to reach the destination point of each special road.
- The states in the priority queue are
(cost, x, y), representing the minimum cost to reach point(x, y). - Initially, populate the priority queue by calculating the cost from
startto each special road's destination (i.e.,cost(start -> road_start) + road_cost). - In the main Dijkstra loop, when visiting a point
u(which is a destination of a special road):- Update the overall minimum cost by considering traveling from
uto thetarget. - For every other special road, calculate the cost of traveling from
uto its destination and update its minimum cost if a shorter path is found.
- Update the overall minimum cost by considering traveling from
Walkthrough
The core idea is to use Dijkstra's algorithm to find the shortest path from the start point to each special road's destination point. The overall minimum cost will be the minimum of the direct path from start to target and paths that go through one or more special roads.
We maintain a dist map to store the minimum cost found so far to reach each special road's destination. A priority queue stores (cost, point) tuples, ordered by cost.
- The initial best answer is the Manhattan distance from
starttotarget. - We begin by considering paths from
startthat use exactly one special road. For each special road, we calculatecost = manhattan(start, road_start) + road_cost. We update thedistmap forroad_endand push{cost, road_end}to the priority queue. - Then, we run Dijkstra's. We repeatedly extract the point
uwith the minimum cost from the priority queue. - From
u, we can either go directly to thetarget. We update our overall best answer withcost[u] + manhattan(u, target). - Or, from
u, we can travel to the start of any other special roadj, take that road, and arrive at its destination. The cost for this new path iscost[u] + manhattan(u, road_start_j) + road_cost_j. If this path is shorter, we update the distance toroad_end_jand add it to the priority queue.
This process continues until the priority queue is empty, guaranteeing we have found the minimum costs to all reachable special road destinations and, by extension, the minimum cost to the target.
import java.util.*; class Solution { private long manhattanDist(int[] p1, int[] p2) { return Math.abs((long)p1[0] - p2[0]) + Math.abs((long)p1[1] - p2[1]); } public int minimumCost(int[] start, int[] target, int[][] specialRoads) { long minCost = manhattanDist(start, target); Map<Long, Long> dist = new HashMap<>(); PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); for (int[] road : specialRoads) { long startToRoadStartCost = manhattanDist(start, new int[]{road[0], road[1]}); long totalCost = startToRoadStartCost + road[4]; long roadDestKey = (long)road[2] * 100001L + road[3]; if (totalCost < dist.getOrDefault(roadDestKey, Long.MAX_VALUE)) { dist.put(roadDestKey, totalCost); pq.offer(new long[]{totalCost, road[2], road[3]}); } } while (!pq.isEmpty()) { long[] current = pq.poll(); long cost = current[0]; int[] u = new int[]{(int)current[1], (int)current[2]}; long uKey = (long)u[0] * 100001L + u[1]; if (cost > dist.getOrDefault(uKey, Long.MAX_VALUE)) { continue; } minCost = Math.min(minCost, cost + manhattanDist(u, target)); for (int[] road : specialRoads) { long uToRoadStartCost = manhattanDist(u, new int[]{road[0], road[1]}); long totalCost = cost + uToRoadStartCost + road[4]; long roadDestKey = (long)road[2] * 100001L + road[3]; if (totalCost < dist.getOrDefault(roadDestKey, Long.MAX_VALUE)) { dist.put(roadDestKey, totalCost); pq.offer(new long[]{totalCost, road[2], road[3]}); } } } return (int) minCost; }}Complexity
Time
O(N^2), where N is the number of special roads. In the worst case, Dijkstra's algorithm will process each of the N destination points. From each point, it iterates through all N special roads to find subsequent paths. With a priority queue, this leads to a complexity around O(N^2).
Space
O(N), where N is the number of special roads. This is for the distance map and the priority queue, which store information for at most N unique destination points.
Trade-offs
Pros
Very efficient in both time and space.
Reduces the number of nodes in the Dijkstra search compared to the explicit graph approach, potentially leading to better performance.
The implementation is clean and directly models the decision-making process at each step.
Cons
The logic can be slightly less intuitive than building a standard graph, as it's tailored to the problem's structure.
Solutions
Solution
class Solution {public int minimumCost(int[] start, int[] target, int[][] specialRoads) { int ans = 1 << 30; int n = 1000000; PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]); Set<Long> vis = new HashSet<>(); q.offer(new int[]{0, start[0], start[1]}); while (!q.isEmpty()) { var p = q.poll(); int x = p[1], y = p[2]; long k = 1L * x * n + y; if (vis.contains(k)) { continue; } vis.add(k); int d = p[0]; ans = Math.min(ans, d + dist(x, y, target[0], target[1])); for (var r : specialRoads) { int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3], cost = r[4]; q.offer(new int[]{d + dist(x, y, x1, y1) + cost, x2, y2}); } } return ans; }private int dist(int x1, int y1, int x2, int y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); }}class Solution {public: int minimumCost(vector<int> &start, vector<int> &target, vector<vector<int>> &specialRoads) { auto dist = [](int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); }; int ans = 1 << 30; int n = 1e6; priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq; pq.push({0, start[0], start[1]}); unordered_set<long long> vis; while (!pq.empty()) { auto [d, x, y] = pq.top(); pq.pop(); long long k = 1LL * x * n + y; if (vis.count(k)) { continue; } vis.insert(k); ans = min(ans, d + dist(x, y, target[0], target[1])); for (auto &r : specialRoads) { int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3], cost = r[4]; pq.push({d + dist(x, y, x1, y1) + cost, x2, y2}); } } return ans; }};class Solution: def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int: def dist(x1: int, y1: int, x2: int, y2: int) -> int: return abs(x1 - x2) + abs(y1 - y2) q = [(0, start[0], start[1])] vis = set() ans = inf while q: d, x, y = heappop(q) if (x, y) in vis: continue vis . add((x, y)) ans = min(ans, d + dist(x, y, * target)) for x1, y1, x2, y2, cost in specialRoads: heappush(q, (d + dist(x, y, x1, y1) + cost, x2, y2)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.