leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1976.cpp (1077B)

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 };