Editorial: LeetCode 1928 Minimum Cost to Reach Destination in Time
https://leetcode.com/problems/minimum-cost-to-reach-destination-in-time/ from Facebook
Thinking process:
This is a single source shortest path problem. The only difference is that we use cost to replace the distance in this problem. As a result, we can just use Dijkstra’s algorithm. We always want to expand our graph by picking the minimum cost node. There’s small variance here: we have another constraint of time.
To deal with the time, we create a tuple of (cost, time, index). For each node we visit, we record the tuple and put it into a priority_queue (heap). This allows us to always pick the smallest cost one first. If there’s a tie in the cost, we’ll pick the smallest time one. This makes sense because we have more chance to reach the destination if we use less time.
If the time is already more than maxTime, we’ll not proceed with this route. Also, for each node, if the time we reach to the node is greater than before, we skip this route as well because the current route must use more cost and time than before, which makes no sense to proceed with this route. If the time is smaller than before, we update the cache and push the tuple to the priority_queue.
1if (newTime <= maxTime and newTime < visited[target]) {
2 if (target == N-1) {
3 return c + passingFees[target];
4 }
5 visited[target] = newTime;
6 pq.push({c+passingFees[target], newTime, target});
7}
The only thing we need to notice here is that there might be multiple edges for the same pair of nodes. We should only keep the smallest time one, which is why I have below condition.
1if (es[x][y] == 0 or t < es[x][y]) {
2 es[x][y] = t;
3 es[y][x] = t;
4}
Other than that, all of the code is a standard way for Dijkstra’s algorithm. We need to be very familiar with this template before the interview.
Here is the code.
1class Solution {
2public:
3 typedef tuple<int, int, int> tiii;
4 int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
5 int N = passingFees.size();
6 priority_queue<tiii, vector<tiii>, greater<tiii>> pq;
7 pq.push({passingFees[0], 0, 0});
8 unordered_map<int, unordered_map<int, int>> es;
9 for (auto& e : edges) {
10 int x = e[0], y = e[1], t = e[2];
11 if (es[x][y] == 0 or t < es[x][y]) {
12 es[x][y] = t;
13 es[y][x] = t;
14 }
15 }
16 vector<int> visited(N, INT_MAX);
17 visited[0] = 0;
18 while (pq.size()) {
19 auto [c, t, n] = pq.top(); pq.pop();
20 for (auto entry : es[n]) {
21 int target = entry.first, travelTime = entry.second;
22 int newTime = t + travelTime;
23 if (newTime <= maxTime and newTime < visited[target]) {
24 if (target == N-1) {
25 return c + passingFees[target];
26 }
27 visited[target] = newTime;
28 pq.push({c+passingFees[target], newTime, target});
29 }
30 }
31 }
32 return -1;
33 }
34};