Leetcode 803 Solution

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<pair<int, int>>> edges(n);
        for (const auto& flight: flights)
            edges[flight[0]].push_back(make_pair(flight[1], flight[2]));

        vector<int> costs(n, INT_MAX);
        costs[src] = 0;

        queue<tuple<int, int, int>> q;
        q.push(make_tuple(src, 0, 0));

        unordered_map<int, pair<int, int>> s;
        s[0] = make_pair(0, 0);
        for (int i = 0; i < n; i++)
            s[i] = make_pair(INT_MAX, INT_MAX);

        while (q.empty() == false)
        {
            auto t = q.front();
            q.pop();
            auto i = std::get<0>(t);
            auto cost = std::get<1>(t);
            auto stop = std::get<2>(t);

            costs[i] = min(costs[i], cost);

            if (stop > K)
                continue;

            for (auto& neigh: edges[i])
            {
                int j = neigh.first;
                int target_cost = neigh.second + cost;
                int target_stop = stop + 1;

                if (s.find(j) == s.end() ||
                    !(s[j].first < target_cost && s[j].second < target_stop))
                {
                    q.push(make_tuple(neigh.first, target_cost, target_stop));
                    s[j] = make_pair(
                        min(s[j].first, target_cost),
                        min(s[j].second, target_stop)
                    );
                }
            }
        }

        return costs[dst] == INT_MAX ? -1 : costs[dst];
    }
};