K 站中转内最便宜的航班 - C++力扣787题

题目链接：https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

解题思路

这个题目的难度算是中等偏上吧，说跟图沾边嘛，其实也不算是。这题有两个解法，第一个就是多弄一个函数 dfs 走一遍，但是这个怎么说呢，弄不好就很容易超时，而且要弄清楚十分复杂。第二个解法就是弄个 dp 数组来搞，我一开始用的第一个解法超时了，应该是有些地方没想清楚，然后换第二个解法就一步到位了。

首先来初始化 dp 二位数组，dp[i][j] 就是经过 i 个节点到达第 j 号节点所需的最最便宜的距离，因为要求最小值嘛，那我们不妨给个 INT_MAX，然后就是出发点无论走多少次最小值就是不走，所以把出发点 src 在 dp 数组里面设为 0。之后就是根据 i - 1 步来推第 i 步，然后取最小值，到最后只需要找到 dp[k + 1][dst] 就是到终点的最便宜的距离了。

完整代码：

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        int price[k + 2][n];
        for(int i = 0 ; i < k + 2; i++) {
            for(int j = 0; j < n; j++) price[i][j] = INT_MAX;
            price[i][src] = 0;
        }
        for(int i = 1; i < k + 2; i++) {
            for(int j = 0; j < flights.size(); j++) {
                vector<int> f = flights[j];
                if(price[i - 1][f[0]] != INT_MAX) {
                    price[i][f[1]] = min(price[i][f[1]], price[i - 1][f[0]] + f[2]);
                }
            }
        }
        return price[k + 1][dst] == INT_MAX ? -1 : price[k + 1][dst];
    }
};