Untitled

mail@pastecode.io avatar
unknown
plain_text
8 months ago
1.3 kB
0
Indexable
Never
class Solution {
public:
    struct cmp {
        bool operator()(const pair<int,pair<int,int>>& a, const pair<int,pair<int,int>>& b) {
            return a.second.first > b.second.first;
        }
    };

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<pair<int,int>>> adj(n);
        for(auto& flight : flights){
            adj[flight[0]].push_back({flight[1], flight[2]});
        }

        priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, cmp> pq;
        pq.push({src, {0, 0}});

        vector<vector<int>> dist(n, vector<int>(K+2, INT_MAX));
        dist[src][0] = 0;

        while(!pq.empty()){
            auto top = pq.top(); pq.pop();
            int node = top.first;
            int edge = top.second.first;
            int stops = top.second.second;

            if(node == dst) return edge;
            if(stops > K) continue;

            for(auto& [nbrnode, nbrdist] : adj[node]){
                if(edge + nbrdist < dist[nbrnode][stops+1]){
                    dist[nbrnode][stops+1] = edge + nbrdist;
                    pq.push({nbrnode, {dist[nbrnode][stops+1], stops+1}});
                }
            }
        }
        return -1;
    }
};
Leave a Comment