有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，要找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
示例 1：
输入:
n = 3, arr = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
0
/
/100
/
1___100___2
解释:从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200
示例 2：
输入:
n = 3, arr = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
0
\
\500
\
12
解释: 从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500
package com.loo;
import java.util.Arrays;
public class FindCheapPrice {
public static void main(String[] args) {
int[][] arr = {{0,1,100},{1,2,100},{0,2,500}};
int src = 0;
int dst = 2;
int n = 3;
int k = 1;
System.out.println(findCheapPrice(arr , src , dst , n , k));
}
public static int findCheapPrice(int[][] arr , int src , int dst , int n , int k) {
int[][] dist = new int[2][n];
int T = Integer.MAX_VALUE/2;
Arrays.fill(dist[0], T);
Arrays.fill(dist[1], T);
dist[0][src] = 0;
dist[1][src] = 0;
for (int i=0;i<=k;i++) {
for (int[] a : arr) {
dist[i&1][a[1]] = Math.min(dist[i&1][a[1]], dist[~i&1][a[0]] + a[2]);
}
}
return dist[k&1][dst] < T ? dist[k&1][dst] : -1;
}
}
