LeetCode 787.K站中转内最便宜的航班

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。如果没有这样的路线，则输出 -1。

示例 1：

输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释:
城市航班图如下

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释:
城市航班图如下

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：

n 范围是 [1, 100]，城市标签从 0 到 n - 1
航班数量范围是 [0, n * (n - 1) / 2]
每个航班的格式 (src, dst, price)
每个航班的价格范围是 [1, 10000]
k 范围是 [0, n - 1]
航班没有重复，且不存在自环

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops

问题分析： 我们必须得定义好dp数组的含义，我一开始定义的是dp[i][j]表示第i站到第j站的最小花费，但很明显无法与前一个取得联系，无法进行状态转移。所以得看到最多中转k站这个点。于是我们定义dp[i][k]表示从src到第i站中转k站的最小花费。

代码如下：

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<int>> dp(n,vector<int>(K+2,INT_MAX));
        for(int i=0;i<=K+1;i++){
            dp[src][i]=0;  //初始化，src到src的花费是0
        }
        for(int k=1;k<=K+1;k++){
            for(vector<int>& flight:flights){
                //这里if表示必须以src为起点
                if(dp[flight[0]][k-1]!=INT_MAX){
                    //两个选择，不中转和中转
                    dp[flight[1]][k]=min(dp[flight[1]][k],dp[flight[0]][k-1]+flight[2]);
                }
            }
        }
        return dp[dst][K+1]==INT_MAX? -1:dp[dst][K+1];
    }
};