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];}
}
