Untitled

class cmp{
    public:
    bool operator() (const pair<int,pair<int,int>>&a, const pair<int,pair<int,int>> &b){
        return a.second.first > b.second.first;
    }
};

class Solution {
public:

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

        //int n=flights.size();
        vector<vector<pair<int,int>>>adj(n);
        for(auto i:flights) adj[i[0]].push_back({i[1],i[2]}); //node-nbr,cost


        vector<vector<int>>dp(n+1,vector<int>(k+2,INT_MAX)); //dp[a][b]- price to go from src to a with b stops
        priority_queue< pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,cmp> pq; //node,dist,stops
        
        dp[src][0]=0;
        pq.push({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 it:adj[node]){
                int nbr_node=it.first;
                int edge_cost=it.second;

                if(edge+edge_cost<dp[nbr_node][stops+1]){
                    dp[nbr_node][stops+1]=edge+edge_cost;
                    pq.push({nbr_node,{dp[nbr_node][stops+1],stops+1}});
                }
            }
        }
    return -1;
    }
};