Number of Restricted Paths From First to Last Node LeetCode solution in C++

1
typedef pair<int, int> pii;
2
class Solution {
3
 public:
4
  int countRestrictedPaths(int n, vector<vector<int>> &edges) {
5
    unordered_map<int, vector<pair<int, int>>> gp;
6
    for (auto &edge : edges) {
7
      gp[edge[0]].push_back({edge[1], edge[2]});
8
      gp[edge[1]].push_back({edge[0], edge[2]});
9
    }
10

11
    vector<int> dist(n + 1, INT_MAX);
12
    priority_queue<pii, vector<pii>, greater<pii>> pq;
13
    pq.push({0, n});
14
    dist[n] = 0;
15

16
    int u, v, w;
17
    while (!pq.empty()) {
18
      pii p = pq.top();
19
      pq.pop();
20
      u = p.second;
21
      for (auto &to : gp[u]) {
22
        v = to.first, w = to.second;
23
        if (dist[v] > dist[u] + w) {
24
          dist[v] = dist[u] + w;
25
          pq.push({dist[v], v});
26
        }
27
      }
28
    }
29
    vector<int> dp(n + 1, -1);
30
    return dfs(gp, n, dp, dist);
31
  }
32

33
  int dfs(unordered_map<int, vector<pair<int, int>>> &gp, int s, vector<int> &dp,
34
          vector<int> &dist) {
35
    int mod = 1e9 + 7;
36
    if (s == 1) return 1;
37
    if (dp[s] != -1) return dp[s];
38
    int sum = 0, weight, val;
39
    for (auto &n : gp[s]) {
40
      weight = dist[s];
41
      val = dist[n.first];
42
      if (val > weight) {
43
        sum = (sum % mod + dfs(gp, n.first, dp, dist) % mod) % mod;
44
      }
45
    }
46
    return dp[s] = sum % mod;
47
  }
48
};