787. Cheapest Flights Within K Stops

[namespace-io]

bellmanford

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<int> dist(n, 1e8);
        dist[src] = 0;
        for(int i = 0; i <= K; i++){
            vector<int> D(dist);
            for(auto &e : flights){
                D[e[1]] = min(dist[e[0]] + e[2], D[e[1]]);
            }
            dist = D;
        }
        
        return dist[dst] == 1e8 ? -1 : dist[dst];
    }
};