Minimum Cost to Reach Destination in Time LeetCode solution in C++

1
typedef pair<int, pair<int, int>> pii;
2

3
class Solution {
4
 public:
5
  int minCost(int maxTime, vector<vector<int>> &edges, vector<int> &passingFees) {
6
    int n = passingFees.size();
7

8
    // state of dp(i,j) : stores the min cost to reach city 'i' in 'j' max time;
9
    int dp[n][maxTime + 1];
10

11
    // without using another array for time will result in TLE since it will
12
    // explore more paths, hence using another array that stores the min time
13
    // the city was discovered. This improves the TC to a huge extent as it
14
    // prunes some path.
15

16
    int ttime[n];
17
    for (int i = 0; i < n; i++) {
18
      ttime[i] = INT_MAX;
19
      for (int j = 0; j <= maxTime; j++) {
20
        dp[i][j] = INT_MAX;
21
      }
22
    }
23
    ttime[0] = 0;
24
    dp[0][0] = passingFees[0];
25

26
    vector<vector<int>> adj[n];
27
    for (auto x : edges) {
28
      adj[x[0]].push_back({x[1], x[2]});
29
      adj[x[1]].push_back({x[0], x[2]});
30
    }
31

32
    // first priority is to minimise the cost associated with the path, {cost,
33
    // city, time}
34
    priority_queue<pii, vector<pii>, greater<pii>> minHeap;
35
    minHeap.push({passingFees[0], {0, 0}});
36

37
    while (!minHeap.empty()) {
38
      auto top = minHeap.top();
39
      minHeap.pop();
40

41
      int u = top.second.first;
42
      int time = top.second.second;
43
      int cost = top.first;
44

45
      if (u == n - 1) return cost;
46

47
      ttime[u] = time;
48

49
      for (auto x : adj[u]) {
50
        // this is the pruning part, where we are only exploring paths that can
51
        // be reached earlier than
52
        // the time already required.
53
        if (time + x[1] < ttime[x[0]]) {
54
          if (time + x[1] <= maxTime) {
55
            // now we are checking if the cost to reach the neighbor is less
56
            // than the already minimum cost, denoted by dp[x[0]][time+x[1]],
57
            // denoting min cost to reach x[0] in 'time+x[1]' max time.
58
            if (cost + passingFees[x[0]] < dp[x[0]][time + x[1]]) {
59
              dp[x[0]][time + x[1]] = cost + passingFees[x[0]];
60
              ttime[x[0]] = time + x[1];
61
              minHeap.push({dp[x[0]][time + x[1]], {x[0], time + x[1]}});
62
            }
63
          }
64
        }
65
      }
66
    }
67
    return -1;
68
  }
69
};