leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1976.cpp (1077B)

      1 class Solution {
      2     const int MOD = 1e9 + 7;
      3     typedef pair<long long, int> road;
      4 
      5   public:
      6     int countPaths(int n, vector<vector<int>> &roads) {
      7         vector<vector<road>> adj(n);
      8         for (auto &r : roads) {
      9             adj[r[0]].push_back({r[2], r[1]});
     10             adj[r[1]].push_back({r[2], r[0]});
     11         }
     12 
     13         priority_queue<road, vector<road>, greater<road>> pq;
     14         vector<long long> dist(n, LONG_MAX);
     15         vector<int> count(n);
     16         pq.push({0, 0});
     17         count[0] = 1;
     18         dist[0] = 0;
     19         while (!pq.empty()) {
     20             auto [w, e] = pq.top();
     21             pq.pop();
     22             if (w > dist[e]) continue;
     23             for (auto [time, v] : adj[e]) {
     24                 if (dist[v] < w + time) continue;
     25                 if (dist[v] == w + time) {
     26                     count[v] = (count[v] + count[e]) % MOD;
     27                     continue;
     28                 }
     29                 dist[v] = w + time;
     30                 count[v] = count[e];
     31                 pq.push({dist[v], v});
     32             }
     33         }
     34         return count[n - 1];
     35     }
     36 };