787

#define TUP tuple<int, int, int>
class Solution {
public:
    int findCheapestPrice(int N, vector<vector<int>>& flights, int src, int dst, int k) {
        //make a graph out of the input
        vector<pair<int, int>> graph[N+1];
        for(vector<int> vc : flights){
            graph[vc[0]].push_back({vc[1], vc[2]});
        }
        //use a dist array can also be used for other destinations(Solutions like this Helpful in interviews)
        vector<int> dist(N, INT_MAX);
        //define a queue and intiallize with src, 0 stops and 0 dist to source itself
        queue<TUP> q;
        q.push({src, 0, 0});

        while(!q.empty()){
            //destructure values this is similar to -> int start = q.front().first, stops = q.front().second
            auto [start, stops, cost] = q.front();
            q.pop();
            //crucial work take the min
            dist[start] = min(dist[start], cost);

            //edge cases to break
            if(start == dst)
                continue;
            if(stops > k)
                continue;
            //traverse adjacent nodes
            for(auto u : graph[start]){
                auto [node, weight] = u;
                //only push if giving better results
                if(cost+weight < dist[node]){
                    q.push({node, stops+1, cost+weight});
                }
            }
        }
        //check if not path found
        return dist[dst] == INT_MAX ? -1 : dist[dst];
    }
};

----------------------------------------------

class Solution {
public:
    int findCheapestPrice(int N, vector<vector<int>>& flights, int src, int dst, int k) {
        k++;
        const int INF = int(1e9);
        vector<vector<int>> dist(N, vector<int>(k+1, INF));

        dist[src][0] = 0;
        for(int i=0; i<k; i++){
            if(i>0){
                for(int j=0; j<N; j++)
                    dist[j][i] = min(dist[j][i], dist[j][i-1]);
            }
            for(auto e: flights){
                int from = e[0], to=e[1], cost=e[2];
                if(dist[from][i] == INF) continue;
                if(dist[from][i]+cost < dist[to][i+1])
                    dist[to][i+1] = dist[from][i]+cost;
            }
        }
        return dist[dst][k] == INF ? -1 : dist[dst][k];
    }
};