2662. Minimum Cost of a Path With Special Roads
Problem Description
You are placed on a grid at a starting position defined by coordinates [startX, startY]
. Your goal is to move to a target position on the grid, specified by [targetX, targetY]
. The cost of moving from any position (x1, y1)
to another (x2, y2)
is equal to the sum of the absolute differences of their x-coordinates and y-coordinates, i.e., |x2 - x1| + |y2 - y1|
.
In addition to the regular cost of moving on the grid, there are special roads available. These are described in a list where each element is another list of the form [x1_i, y1_i, x2_i, y2_i, cost_i]
, representing a special road that connects (x1_i, y1_i)
to (x2_i, y2_i)
at a given cost_i
. You can use these special roads multiple times if needed.
The challenge is to determine the minimum cost to move from the start position to the target position, considering the regular grid movement cost and any cost savings that can be achieved by using the special roads.
Intuition
To find the least costly path, we need an algorithm that can process the grid and special roads systematically while keeping track of the costs accumulated along the way. The most suitable algorithm for this problem is Dijkstra's algorithm. It’s a well-known algorithm designed to find the shortest path in a weighted graph with non-negative edge weights.
Dijkstra's algorithm fits our needs well because it uses a priority queue to explore nodes (positions) that have the smallest known cost to reach from the start. It updates the cost to reach neighboring nodes as it progresses, and it's greedy in nature, always choosing the least costly option to explore next.
The default movement cost across the grid can act as the edges with a regular weight, while the paths provided by the special roads can be seen as edges with potentially lower weights. The main difference here is that Dijkstra's algorithm typically operates on graphs with fixed nodes and edges, whereas in this problem, the edges are dynamic, as movement is not restricted to predefined connections between points.
By using a modified version of Dijkstra's algorithm, we can push into the priority queue the cost to move from the current position to every position that can be reached by a special road, while also considering the cost to move directly towards the target position from our current position. This approach systematically evaluates all possible moves (both regular and special), keeping track of visited positions to prevent circular routes and redundant calculations.
In summary, the intuition is to use a priority queue to greedily accumulate the least cost of reaching the adjacent positions or the target, considering the cost of normal moves and special roads, until we can determine the minimum cost required to reach the target.
Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.
Solution Approach
The solution is implemented using Dijkstra's algorithm, a classical algorithm used in computing the shortest paths in a weighted graph. The specific data structures and patterns used in this implementation are:
-
A Priority Queue: This is used to maintain a set of all unvisited nodes, allowing for nodes to be processed in order based on their current known cost from the start. In Python, this is typically implemented with a min-heap using the
heapq
library. -
A Set for Visited Nodes: To keep track of all visited positions to prevent revisiting and recalculating costs for those positions, a set is used.
In Dijkstra's algorithm, nodes (in this case, grid positions) are visited in order based on their current lowest cost from a start position. For each visited node, we update the costs to its adjacent nodes, which, in the context of the grid problem, are the other nodes that can be reached either directly (one step away in any of the four cardinal directions) or through a special road. The algorithm typically checks if the new path to a node is better than the previously known path, and updates it accordingly.
Here, the dist
function is defined to calculate the cost of moving between two positions on the grid. The priority queue q
is initialized with a tuple containing the starting cost (0), and the x and y coordinates of the starting position.
1def dist(x1: int, y1: int, x2: int, y2: int) -> int:
2 return abs(x1 - x2) + abs(y1 - y2)
3
4q = [(0, start[0], start[1])]
The solution maintains a loop iterating over the priority queue until it is empty, meaning all reachable positions have been considered.
1while q: 2 d, x, y = heappop(q)
Then it checks if the current position has been visited before:
1if (x, y) in vis: 2 continue
If not, the current position is added to the visited set, and we calculate the cost to reach the target from here:
1vis.add((x, y))
2ans = min(ans, d + dist(x, y, *target))
The algorithm then considers all special roads, pushing the cost of traveling via each special road from the current node into the priority queue. This cost includes the distance from the current node to the start of the special road plus the special road's cost:
1for x1, y1, x2, y2, cost in specialRoads: 2 heappush(q, (d + dist(x, y, x1, y1) + cost, x2, y2))
Once the queue q
is empty, the variable ans
will contain the minimum cost to reach the target position, which is then returned.
Overall, the algorithm uses Dijkstra's pattern for pathfinding in an efficient manner, yielding the minimum cost considering both normal grid costs and special roads.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's assume we start at position [0, 0]
and aim to reach the target at position [2, 2]
. The grid allows us to move at the cost of the Manhattan distance between points, which is the sum of the absolute differences in the x and y coordinates. On top of the regular movement, we have special roads that connect certain points at a potentially reduced cost. Let's consider one special road for our example that connects [1, 1]
to [2, 2]
with a cost
of 1
.
Now let's walk through how the algorithm works using Dijkstra's algorithm:
-
We initialize our priority queue
q
with the starting position[(0, 0, 0)]
which represents a0
cost to reach[0, 0]
. -
We also initialize a
visited
setvis
to keep track of the positions we've already considered to avoid calculating them again. -
We start by popping the first item from our priority queue: the starting position
(0, 0, 0)
, with0
being the cost so far. -
Since
[0, 0]
isn't in ourvisited
set, we process it. We calculate the Manhattan distance to our target[2, 2]
, which is4
, and we add the current position to thevisited
set. -
Now, we consider the available special roads. In our case, there's one that goes from
[1, 1]
to[2, 2]
. We calculate the cost to get to the starting point of the special road, which is2
(from[0, 0]
to[1, 1]
), and then add thecost
of the special road (1
). -
We put the endpoint of the special road
[2, 2]
into our priority queue with the calculated cost to get there (a total of3
). -
Now the priority queue has one item,
[3, 2, 2]
, which we then pop. Since this is the target and we haven't visited it before, we check the total cost required to reach here and update our answerans
if it's lower than any previous one. -
As there are no other positions to process (the priority queue is empty, and there is only one special road in our example), the algorithm ends. The minimum cost is
3
, which is lower than the straight Manhattan distance to the target, demonstrating the use of the special road to reduce costs.
In a more complex scenario with multiple special roads and a larger grid, the algorithm would work similarly, considering all possible moves and special roads from each position visited, updating the priority queue and visited
set accordingly until the minimum cost to reach the target is found.
Solution Implementation
1from heapq import heappush, heappop
2from typing import List
3from math import inf
4
5class Solution:
6 def minimum_cost(self, start: List[int], target: List[int], special_roads: List[List[int]]) -> int:
7 # Calculates Manhattan distance between two points (x1, y1) and (x2, y2)
8 def calculate_distance(x1: int, y1: int, x2: int, y2: int) -> int:
9 return abs(x1 - x2) + abs(y1 - y2)
10
11 # Initialize a priority queue with a tuple containing distance, x coordinate, and y coordinate
12 priority_queue = [(0, start[0], start[1])]
13 # This set will keep track of visited points to prevent revisiting
14 visited = set()
15 # Initialize answer as infinity to track minimum cost
16 minimum_cost = inf
17
18 # Process nodes in the priority queue
19 while priority_queue:
20 # Pop the node with the lowest distance from the priority queue
21 distance, x, y = heappop(priority_queue)
22 # If the node has already been visited, skip it
23 if (x, y) in visited:
24 continue
25 # Otherwise, add it to the visited set
26 visited.add((x, y))
27 # Update the minimum cost if the new cost is lower
28 minimum_cost = min(minimum_cost, distance + calculate_distance(x, y, *target))
29 # Check neighboring special roads
30 for x1, y1, x2, y2, cost in special_roads:
31 # Compute total cost to reach the end of the special road
32 total_cost = distance + calculate_distance(x, y, x1, y1) + cost
33 # Add the end point of the special road to the priority queue
34 heappush(priority_queue, (total_cost, x2, y2))
35
36 # Return the minimum cost to reach the target
37 return minimum_cost
38
1class Solution {
2 // Method to calculate the minimum cost to travel from the start point to the target point considering special roads
3 public int minimumCost(int[] start, int[] target, int[][] specialRoads) {
4 // A large constant for the initial minimum cost
5 int minCost = Integer.MAX_VALUE;
6 // Size of the grid
7 int gridSize = 1000000;
8 // Priority Queue to store states with minimum distance at the top
9 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
10 // Set for visited points to avoid processing a point multiple times
11 Set<Long> visited = new HashSet<>();
12 // Add the starting point to the priority queue with initial cost 0
13 priorityQueue.offer(new int[] {0, start[0], start[1]});
14 // Process nodes until the priority queue is empty
15 while (!priorityQueue.isEmpty()) {
16 int[] point = priorityQueue.poll();
17 int currentX = point[1], currentY = point[2];
18 // Unique number for the current point (hash)
19 long hash = 1L * currentX * gridSize + currentY;
20 // Skip if we've already visited this point
21 if (visited.contains(hash)) {
22 continue;
23 }
24 visited.add(hash);
25 // Current distance from start to the point
26 int distance = point[0];
27 // Update minimum cost with the sum of the current distance and direct distance from the current point to target
28 minCost = Math.min(minCost, distance + calculateManhattanDistance(currentX, currentY, target[0], target[1]));
29 // Explore special roads from the current point
30 for (int[] road : specialRoads) {
31 int roadStartX = road[0], roadStartY = road[1], roadEndX = road[2], roadEndY = road[3], roadCost = road[4];
32 // Offer a new state to the queue with the updated cost considering the special road
33 priorityQueue.offer(new int[] {
34 distance + calculateManhattanDistance(currentX, currentY, roadStartX, roadStartY) + roadCost,
35 roadEndX,
36 roadEndY
37 });
38 }
39 }
40 // Return the minimum cost found
41 return minCost;
42 }
43
44 // Helper method to calculate Manhattan distance between two points
45 private int calculateManhattanDistance(int x1, int y1, int x2, int y2) {
46 return Math.abs(x1 - x2) + Math.abs(y1 - y2);
47 }
48}
49
1#include <vector>
2#include <queue>
3#include <unordered_set>
4#include <cmath>
5#include <tuple>
6
7class Solution {
8public:
9 int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
10 // Lambda function to calculate Manhattan distance between two points
11 auto calculateDistance = [](int x1, int y1, int x2, int y2) {
12 return std::abs(x1 - x2) + std::abs(y1 - y2);
13 };
14
15 // Initialize the answer to a large number
16 int minimumCost = INT_MAX;
17 // Define a very large value to be used as a hashing multiplier
18 int hashMultiplier = 1e6;
19 // Priority queue to maintain the frontier of the search
20 std::priority_queue<std::tuple<int, int, int>,
21 std::vector<std::tuple<int, int, int>>,
22 std::greater<std::tuple<int, int, int>>> frontier;
23
24 // Push the starting position with cost 0 into the priority queue
25 frontier.push({0, start[0], start[1]});
26 // Set to keep track of visited positions
27 std::unordered_set<long long> visited;
28
29 while (!frontier.empty()) {
30 // Dequeue the closest (in terms of cost) position from the frontier
31 auto [currentCost, currentX, currentY] = frontier.top();
32 frontier.pop();
33
34 // Calculate the hash value of the current position
35 long long hashValue = static_cast<long long>(currentX) * hashMultiplier + currentY;
36
37 if (visited.count(hashValue)) {
38 // Skip if this position has already been visited
39 continue;
40 }
41
42 // Mark the current position as visited
43 visited.insert(hashValue);
44
45 // Update minimum cost considering the current path and direct path to the target
46 minimumCost = std::min(minimumCost, currentCost + calculateDistance(currentX, currentY, target[0], target[1]));
47
48 // For each special road, calculate costs and push new positions to the queue
49 for (auto& road : specialRoads) {
50 int startRoadX = road[0], startRoadY = road[1];
51 int endRoadX = road[2], endRoadY = road[3];
52 int roadCost = road[4];
53
54 // Calculate cost to the start of the special road plus the road's cost
55 int newCost = currentCost + calculateDistance(currentX, currentY, startRoadX, startRoadY) + roadCost;
56
57 // Push the special road's end position with the updated cost into the queue
58 frontier.push({newCost, endRoadX, endRoadY});
59 }
60 }
61
62 // Return the calculated minimum cost
63 return minimumCost;
64 }
65};
66
1// Define comparator type for usage in the heap.
2type Comparator<T> = (lhs: T, rhs: T) => number;
3
4// Define the global heap structure with comparator.
5let heapData: Array<any | null>;
6let heapComparator: (i: number, j: number) => boolean;
7
8// Calculate Manhattan distance between two points.
9const calculateDistance = (x1: number, y1: number, x2: number, y2: number): number => {
10 return Math.abs(x1 - x2) + Math.abs(y1 - y2);
11};
12
13// Represents the priority queue using heap.
14const heapPush = (heap: any, element: any): void => {
15 heap.push(element);
16 let index = heapSize();
17 while (index >> 1 !== 0 && heapComparator(index, index >> 1)) heapSwap(heap, index, (index >>= 1));
18};
19
20const heapPop = (heap: any): any => {
21 heapSwap(heap, 1, heapSize());
22 const top = heap.pop();
23 heapify(1);
24 return top;
25};
26
27const heapSize = (): number => {
28 return heapData.length - 1;
29};
30
31const heapify = (index: number): void => {
32 while (true) {
33 let smallest = index;
34 const left = index * 2;
35 const right = index * 2 + 1;
36 const size = heapData.length;
37 if (left < size && heapComparator(left, smallest)) smallest = left;
38 if (right < size && heapComparator(right, smallest)) smallest = right;
39 if (smallest !== index) {
40 heapSwap(heapData, index, smallest);
41 index = smallest;
42 } else break;
43 }
44};
45
46const heapSwap = (heap: any, i: number, j: number): void => {
47 [heap[i], heap[j]] = [heap[j], heap[i]];
48};
49
50// Calculates the minimum cost to reach a target point from a start point, given special roads that can be used.
51const minimumCost = (start: number[], target: number[], specialRoads: number[][]): number => {
52 heapData = [null];
53 heapComparator = (i, j) => heapData[i][0] < heapData[j][0];
54 heapPush(heapData, [0, start[0], start[1]]);
55
56 const n = 1000000;
57 const visited = new Set();
58 let ans = Infinity;
59
60 while (heapSize()) {
61 const [distance, x, y] = heapPop(heapData);
62 const key = x * n + y;
63 if (visited.has(key)) {
64 continue;
65 }
66 visited.add(key);
67 ans = Math.min(ans, distance + calculateDistance(x, y, target[0], target[1]));
68
69 for (const [x1, y1, x2, y2, cost] of specialRoads) {
70 heapPush(heapData, [distance + calculateDistance(x, y, x1, y1) + cost, x2, y2]);
71 }
72 }
73
74 return ans;
75};
76
77// Set the comparator for the heap as a global definition which compares two elements based on their distance.
78const setComparator = (compareFunction: Comparator<any>): void => {
79 heapComparator = (i, j) => compareFunction(heapData[i], heapData[j]) < 0;
80};
81
82// Initialize the heap with null at index 0 for easy index calculations.
83const initializeHeap = (): void => {
84 heapData = [null];
85};
86
87// Initialize heap with custom comparator if provided.
88setComparator((lhs, rhs) => (lhs[0] < rhs[0] ? -1 : lhs[0] > rhs[0] ? 1 : 0));
89
Time and Space Complexity
The time complexity of the given code is O(n^2 \times \log n)
, where n
is the number of special roads. This complexity arises because, in the worst case, each road is visited once and every time a road is visited, it could potentially lead to all other roads being considered as next steps. For each road, the distance to the next road is computed, which is an O(1)
operation, but then a point is added to the priority queue that has a size up to O(n^2)
(since every special road could be pushed to the queue with different starting points), and hence, the insertion time will be O(\log n^2)
which simplifies to O(2\log n) = O(\log n)
. Since we could have O(n^2)
insertions, the total time complexity is O(n^2 \times \log n)
.
The space complexity of the code is O(n^2)
mainly due to the storage requirements of the priority queue and the visited set. In the worst case, each point in the grid could be added to the visited set and at most, every entry of the special roads could be stored in the priority queue simultaneously, if the points are all unique.
Learn more about how to find time and space complexity quickly using problem constraints.
How many ways can you arrange the three letters A, B and C?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.