Number of Ways to Arrive at Destination LeetCode solution in C++

1
class Solution {
2
 public:
3
  int countPaths(int n, vector<vector<int>> &roads) {
4
    int mod = 1e9 + 7;
5
    vector<vector<pair<int, int>>> graph(n);
6
    for (auto &road : roads) {
7
      graph[road[0]].push_back({road[1], road[2]});
8
      graph[road[1]].push_back({road[0], road[2]});
9
    }
10

11
    vector<long long> distance(n, LONG_MAX);
12
    vector<int> path(n, 0);
13

14
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
15
                   greater<pair<long long, int>>>
16
        pq;
17
    pq.push({0, 0});
18
    distance[0] = 0;
19
    path[0] = 1;
20

21
    while (!pq.empty()) {
22
      pair<long long, int> t = pq.top();
23
      pq.pop();
24

25
      for (auto &nbr : graph[t.second]) {
26
        long long vert = nbr.first;
27
        long long edge = nbr.second;
28

29
        if (distance[vert] > distance[t.second] + edge) {
30
          distance[vert] = distance[t.second] + edge;
31
          pq.push({distance[vert], vert});
32
          path[vert] = path[t.second] % mod;
33
        } else if (distance[vert] == t.first + edge) {
34
          path[vert] += path[t.second];
35
          path[vert] %= mod;
36
        }
37
      }
38
    }
39

40
    return path[n - 1];
41
  }
42
};