leetcode

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

0787.cpp (863B)

      1 class Solution {
      2     struct edge {
      3         int d, w, s;
      4         edge(int d, int w, int s = -1) : d(d), w(w), s(s) {}
      5         friend bool operator<(const edge &e1, const edge &e2) { return e1.w > e2.w; }
      6     };
      7 
      8   public:
      9     int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
     10         vector<vector<edge>> adj(n);
     11         for (auto &f : flights)
     12             adj[f[0]].push_back({f[1], f[2]});
     13 
     14         vector<int> stop(n, INT_MAX);
     15         priority_queue<edge> pq;
     16 
     17         pq.push({src, 0, 0});
     18         while (!pq.empty()) {
     19             auto [d, w, s] = pq.top();
     20             pq.pop();
     21             if (s > stop[d] || s > k + 1) continue;
     22 
     23             stop[d] = s;
     24             if (d == dst) return w;
     25             for (auto [d1, w1, _] : adj[d])
     26                 pq.push({d1, w + w1, s + 1});
     27         }
     28         return -1;
     29     }
     30 };