leetcode

0 class Solution {

1 const int MOD = 1e9 + 7;

2 typedef pair<long long, int> road;

3

4 public:

5 int countPaths(int n, vector<vector<int>> &roads) {

6 vector<vector<road>> adj(n);

7 for (auto &r : roads) {

8 adj[r[0]].push_back({r[2], r[1]});

9 adj[r[1]].push_back({r[2], r[0]});

10 }

11

12 priority_queue<road, vector<road>, greater<road>> pq;

13 vector<long long> dist(n, LONG_MAX);

14 vector<int> count(n);

15 pq.push({0, 0});

16 count[0] = 1;

17 dist[0] = 0;

18 while (!pq.empty()) {

19 auto [w, e] = pq.top();

20 pq.pop();

21 if (w > dist[e]) continue;

22 for (auto [time, v] : adj[e]) {

23 if (dist[v] < w + time) continue;

24 if (dist[v] == w + time) {

25 count[v] = (count[v] + count[e]) % MOD;

26 continue;

27 }

28 dist[v] = w + time;

29 count[v] = count[e];

30 pq.push({dist[v], v});

31 }

32 }

33 return count[n - 1];

34 }

35 };