1928. Minimum Cost to Reach Destination in Time LeetCode Solution
In this guide, you will get 1928. Minimum Cost to Reach Destination in Time LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Reach Destination in Time 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.
Problem Statement of Minimum Cost to Reach Destination in Time
There is a country of n cities numbered from 0 to n – 1 where all the cities are connected by bi-directional roads. The roads are represented as a 2D integer array edges where edges[i] = [xi, yi, timei] denotes a road between cities xi and yi that takes timei minutes to travel. There may be multiple roads of differing travel times connecting the same two cities, but no road connects a city to itself.
Each time you pass through a city, you must pay a passing fee. This is represented as a 0-indexed integer array passingFees of length n where passingFees[j] is the amount of dollars you must pay when you pass through city j.
In the beginning, you are at city 0 and want to reach city n – 1 in maxTime minutes or less. The cost of your journey is the summation of passing fees for each city that you passed through at some moment of your journey (including the source and destination cities).
Given maxTime, edges, and passingFees, return the minimum cost to complete your journey, or -1 if you cannot complete it within maxTime minutes.
Input: maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: 11
Explanation: The path to take is 0 -> 1 -> 2 -> 5, which takes 30 minutes and has $11 worth of passing fees.
Example 2:
Input: maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: 48
Explanation: The path to take is 0 -> 3 -> 4 -> 5, which takes 26 minutes and has $48 worth of passing fees.
You cannot take path 0 -> 1 -> 2 -> 5 since it would take too long.
Example 3:
Input: maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
Output: -1
Explanation: There is no way to reach city 5 from city 0 within 25 minutes.
Constraints:
1 <= maxTime <= 1000
n == passingFees.length
2 <= n <= 1000
n – 1 <= edges.length <= 1000
0 <= xi, yi <= n – 1
1 <= timei <= 1000
1 <= passingFees[j] <= 1000
The graph may contain multiple edges between two nodes.
The graph does not contain self loops.
Complexity Analysis
Time Complexity: O((|V| + |E|)\log |V|)
Space Complexity: O(|E| + |V|)
1928. Minimum Cost to Reach Destination in Time LeetCode Solution in C++
class Solution {
public:
int minCost(int maxTime, vector<vector<int>>& edges,
vector<int>& passingFees) {
const int n = passingFees.size();
vector<vector<pair<int, int>>> graph(n);
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
const int w = edge[2];
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
return dijkstra(graph, 0, n - 1, maxTime, passingFees);
}
private:
int dijkstra(const vector<vector<pair<int, int>>>& graph, int src, int dst,
int maxTime, const vector<int>& passingFees) {
// cost[i] := the minimum cost to reach the i-th city
vector<int> cost(graph.size(), INT_MAX);
// dist[i] := the minimum time to reach the i-th city
vector<int> dist(graph.size(), maxTime + 1);
cost[src] = passingFees[src];
dist[src] = 0;
using T = tuple<int, int, int>; // (cost[u], dist[u], u)
priority_queue<T, vector<T>, greater<>> minHeap;
minHeap.emplace(cost[src], dist[src], src);
while (!minHeap.empty()) {
const auto [currCost, d, u] = minHeap.top();
minHeap.pop();
if (u == dst)
return cost[dst];
if (d > dist[u] && currCost > cost[u])
continue;
for (const auto& [v, w] : graph[u]) {
if (d + w > maxTime)
continue;
// Go from u -> v.
if (currCost + passingFees[v] < cost[v]) {
cost[v] = currCost + passingFees[v];
dist[v] = d + w;
minHeap.emplace(cost[v], dist[v], v);
} else if (d + w < dist[v]) {
dist[v] = d + w;
minHeap.emplace(currCost + passingFees[v], dist[v], v);
}
}
}
return -1;
}
}; /* code provided by PROGIEZ */
1928. Minimum Cost to Reach Destination in Time LeetCode Solution in Java
class Solution {
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
final int n = passingFees.length;
List<Pair<Integer, Integer>>[] graph = new List[n];
for (int i = 0; i < n; ++i)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
final int t = edge[2];
graph[u].add(new Pair<>(v, t));
graph[v].add(new Pair<>(u, t));
}
return dijkstra(graph, 0, n - 1, maxTime, passingFees);
}
private int dijkstra(List<Pair<Integer, Integer>>[] graph, int src, int dst, int maxTime,
int[] passingFees) {
int[] cost = new int[graph.length]; // cost[i] := the minimum cost to reach the i-th city
int[] dist = new int[graph.length]; // dist[i] := the minimum distance to reach the i-th city
Arrays.fill(cost, Integer.MAX_VALUE);
Arrays.fill(dist, maxTime + 1);
cost[0] = passingFees[0];
dist[0] = 0;
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])) {
{ offer(new int[] {cost[src], dist[src], src}); } // (cost[u], dist[u], u)
};
while (!minHeap.isEmpty()) {
final int currCost = minHeap.peek()[0];
final int d = minHeap.peek()[1];
final int u = minHeap.poll()[2];
if (u == dst)
return cost[dst];
if (d > dist[u] && currCost > cost[u])
continue;
for (Pair<Integer, Integer> pair : graph[u]) {
final int v = pair.getKey();
final int w = pair.getValue();
if (d + w > maxTime)
continue;
// Go from x -> y
if (currCost + passingFees[v] < cost[v]) {
cost[v] = currCost + passingFees[v];
dist[v] = d + w;
minHeap.offer(new int[] {cost[v], dist[v], v});
} else if (d + w < dist[v]) {
dist[v] = d + w;
minHeap.offer(new int[] {currCost + passingFees[v], dist[v], v});
}
}
}
return -1;
}
} // code provided by PROGIEZ
1928. Minimum Cost to Reach Destination in Time LeetCode Solution in Python
class Solution:
def minCost(
self,
maxTime: int,
edges: list[list[int]],
passingFees: list[int],
) -> int:
n = len(passingFees)
graph = [[] for _ in range(n)]
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
return self._dijkstra(graph, 0, n - 1, maxTime, passingFees)
def _dijkstra(
self,
graph: list[list[tuple[int, int]]],
src: int,
dst: int,
maxTime: int,
passingFees: list[int],
) -> int:
# cost[i] := the minimum cost to reach the i-th city
cost = [math.inf] * len(graph)
# dist[i] := the minimum time to reach the i-th city
dist = [maxTime + 1] * len(graph)
cost[src] = passingFees[src]
dist[src] = 0
minHeap = [(cost[src], dist[src], src)] # (cost[u], dist[u], u)
while minHeap:
currCost, d, u = heapq.heappop(minHeap)
if u == dst:
return cost[dst]
if d > dist[u] and currCost > cost[u]:
continue
for v, w in graph[u]:
if d + w > maxTime:
continue
# Go from u -> v.
if currCost + passingFees[v] < cost[v]:
cost[v] = currCost + passingFees[v]
dist[v] = d + w
heapq.heappush(minHeap, (cost[v], dist[v], v))
elif d + w < dist[v]:
dist[v] = d + w
heapq.heappush(minHeap, (currCost + passingFees[v], dist[v], v))
return -1 # code by PROGIEZ
