Dijkstra

787. Cheapest Flights Within K Stops

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        priority_queue<pair<int, pair<int, int>>> pq;
        vector<vector<pair<int, int>>> graph(n);
        for (auto flight : flights) {
            auto a = flight[0], b = flight[1], cost = flight[2];
            graph[a].emplace_back(b, cost);
        }
        pq.push(make_pair(0, make_pair(src, 0)));
        vector<vector<int>> dis(n, vector<int>(K + 2, INT_MAX));
        dis[src][0] = 0;
        while (!pq.empty()) {
            auto curr_price = - pq.top().first;
            auto [i, stop] = pq.top().second;
            pq.pop();
            if (stop == K + 1 || curr_price > dis[i][stop]) continue;
            for (auto [j, cost] : graph[i]) {
                if (curr_price + cost <  dis[j][stop + 1]) {
                    dis[j][stop + 1] = curr_price + cost;
                    pq.push(make_pair( - (curr_price + cost), make_pair(j, stop + 1)));
                }
            }
        }
        int ret = INT_MAX;
        for (int j = 0; j <= K + 1; ++j)
            ret = min(ret, dis[dst][j]);
        return ret == INT_MAX ? -1 : ret;
    }
};

An improved version based on [1].

typedef tuple<int, int, int> iii;
typedef pair<int, int> ii;
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<ii>> graph(n);
        for (auto& flight : flights) {
            graph[flight[0]].emplace_back(flight[1], flight[2]);
        }
        priority_queue<iii> pq;
        pq.push({0, src, 0});
        while (!pq.empty()) {
            auto [cost_sofa, i, stop] = pq.top();
            pq.pop();
            cost_sofa *= -1;
            if (i == dst) return cost_sofa;
            if (stop == K + 1) continue;
            for (auto& [j, price] : graph[i]) {
                auto new_cost_sofa = cost_sofa + price;
                pq.push({-new_cost_sofa, j, stop + 1});
            }
        }
        return -1;
    }
};

Reference

[1] https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/115541/JavaPython-Priority-Queue-Solution