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].
航班没有重复，且不存在环路
class Solution {
//这个dp是第一个是到的目标的位置，第二个参数是步数
// public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// int dp[][]=new int[n][k+2];
// for(int i=0;i<n;i++)
// Arrays.fill(dp[i],Integer.MAX_VALUE);
// 这里初始化了起始点的距离
// Arrays.fill(dp[src],0);
// for(int per=1;per<=k+1;per++)
// {
// for(int []num:flights)
// {
// int from=num[0];
// int to=num[1];
// int cost=num[2];
// //我当前的路程是不是存在路程，如果不存在就是MAX_VALUE
// //我当前路程的最小值就是
// if(dp[from][per-1]!=Integer.MAX_VALUE) dp[to][per]=Math.min(dp[to][per],dp[from][per-1]+cost);
// }
// }
// return dp[dst][k+1]==Integer.MAX_VALUE?-1:dp[dst][k+1];
// }
//这个dp第一个参数是起始位置，第二个参数是目标位置
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
int[][] dp = new int[n][K+2];
for(int i = 0; i < n; ++i) Arrays.fill(dp[i], Integer.MAX_VALUE);
for(int k = 0; k <= K+1; ++k) dp[src][k] = 0;
for(int k = 1; k <= K+1; ++k) {
for(int[] flight : flights) {
if(dp[flight[0]][k-1] != Integer.MAX_VALUE)
dp[flight[1]][k] = Math.min(dp[flight[1]][k], dp[flight[0]][k-1] + flight[2]);
}
}
return dp[dst][K+1] == Integer.MAX_VALUE ? -1 : dp[dst][K+1];
}
}