leetcode

0 class Solution {

1 struct edge {

2 int d, w, s;

3 edge(int d, int w, int s = -1) : d(d), w(w), s(s) {}

4 friend bool operator<(const edge &e1, const edge &e2) { return e1.w > e2.w; }

5 };

6

7 public:

8 int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {

9 vector<vector<edge>> adj(n);

10 for (auto &f : flights)

11 adj[f[0]].push_back({f[1], f[2]});

12

13 vector<int> stop(n, INT_MAX);

14 priority_queue<edge> pq;

15

16 pq.push({src, 0, 0});

17 while (!pq.empty()) {

18 auto [d, w, s] = pq.top();

19 pq.pop();

20 if (s > stop[d] || s > k + 1) continue;

21

22 stop[d] = s;

23 if (d == dst) return w;

24 for (auto [d1, w1, _] : adj[d])

25 pq.push({d1, w + w1, s + 1});

26 }

27 return -1;

28 }

29 };