787. K 站中转内最便宜的航班 2021-08-24

class Solution {
private:
    const int NOT_CONNECTED = 10000000;
public:
    int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst, int k) {
        vector<vector<int> > G(n, vector<int>(n, NOT_CONNECTED));
        for (auto &flight : flights) {
            G[flight[0]][flight[1]] = flight[2];
        }
        for (int i = 0; i < n; ++i)
            G[i][i] = 0;
        vector<vector<int> > dp(k + 2, vector<int>(n, NOT_CONNECTED));
        dp[0][src] = 0;
        for (int i = 1; i <= k + 1; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int l = 0; l < n; ++l) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][l] + G[l][j]);
                }
            }
        }
        return dp[k + 1][dst] == NOT_CONNECTED ? -1 : dp[k + 1][dst];
    }
};