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.
Example 1:
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 <= 1000n == passingFees.length2 <= n <= 1000n - 1 <= edges.length <= 10000 <= xi, yi <= n - 11 <= timei <= 10001 <= passingFees[j] <= 1000- The graph may contain multiple edges between two nodes.
- The graph does not contain self loops.
Companies:
Facebook
Related Topics:
Dynamic Programming
Intuition: BFS the graph in a way that we expand in the direction with the shortest time, and we log the smallest cost to a node at the same time. If the time already exceeds the maxTime, we stop the BFS.
Algorithm:
We can use Dijkstra for this greedy BFS. We use a min heap to keep track the expandable nodes with the shortest time taken. Each expandable nodes are represented as (node, time, cost) in the min heap.
We keep track of minCost[u] and minTime[u] which are the minimum cost/time to reach node u, respectively.
For a given node (u, time, cost), we try expanding to each of u's neighbor node v.
If the new time is greater than maxTime, we should skip it, i.e. time + edge[u][v] > maxTime
Otherwise, we expand in the following two cases:
- The new cost reaching
vis smaller than before, i.e.cost + fee[v] < minCost[v]. - The time taken to reach
vis smaller than before, i.e.time + edge[u][v] < minTime[v].
In the end, we return minCost[N - 1].
// OJ: https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/
// Author: github.com/lzl124631x
// Time: O(ElogE)
// Space: O(V + E)
class Solution {
typedef array<int, 3> Node; // node, time, cost
public:
int minCost(int maxTime, vector<vector<int>>& E, vector<int>& F) {
int N = F.size();
vector<unordered_map<int, int>> G(N);
vector<int> cost(N, INT_MAX), minTime(N, INT_MAX);
for (auto &e : E) {
int u = e[0], v = e[1], t = e[2];
if (G[u].count(v)) { // For duplicated edges, we just need to keep track of the edge with smallest time.
G[u][v] = min(G[u][v], t);
G[v][u] = min(G[v][u], t);
} else {
G[u][v] = t;
G[v][u] = t;
}
}
auto cmp = [](auto &a, auto &b) { return a[1] > b[1]; }; // min-heap: Heap top is the node with the smallest time to reach
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
pq.push({0, 0, F[0]}); // we start from node `0` whose time is 0 and cost is fee[0]
cost[0] = F[0];
minTime[0] = 0;
while (pq.size()) {
auto [u, time, c] = pq.top();
pq.pop();
for (auto &[v, t] : G[u]) {
int nt = time + t, nc = c + F[v];
if (nt > maxTime) continue; // if time is out of range, skip
if (nc < cost[v]) { // less cost
cost[v] = nc;
minTime[v] = min(minTime[v], nt);
pq.push({v, nt, nc});
} else if (nt < minTime[v]) { // less time
minTime[v] = nt;
pq.push({v, nt, nc});
}
}
}
return cost[N - 1] == INT_MAX ? -1 : cost[N - 1];
}
};We change the min-heap to have the nodes with the smallest cost at the top.
// OJ: https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/
// Author: github.com/lzl124631x
// Time: O(ElogE)
// Space: O(V + E)
class Solution {
typedef array<int, 3> Node; // node, time, cost
public:
int minCost(int maxTime, vector<vector<int>>& E, vector<int>& F) {
int N = F.size();
vector<unordered_map<int, int>> G(N);
vector<int> minTime(N, maxTime + 1);
for (auto &e : E) {
int u = e[0], v = e[1], t = e[2];
if (G[u].count(v)) { // For duplicated edges, we just need to keep track of the edge with smallest time.
G[u][v] = G[v][u] = min(G[u][v], t);
} else {
G[u][v] = G[v][u] = t;
}
}
auto cmp = [](auto &a, auto &b) { return a[2] > b[2]; }; // min-heap: Heap top is the node with the smallest cost to reach
priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);
pq.push({0, 0, F[0]});
minTime[0] = 0;
while (pq.size()) {
auto [u, time, c] = pq.top();
pq.pop();
if (u == N - 1) return c;
for (auto &[v, t] : G[u]) {
int nt = time + t, nc = c + F[v];
if (nt < minTime[v]) {
minTime[v] = nt;
pq.push({v, nt, nc});
}
}
}
return -1;
}
};