2018-09-19 22:34:28
问题描述：
问题求解：
本题是典型的最短路径的扩展题，可以使用Bellman Ford算法进行求解，需要注意的是在Bellman Ford算法的时候需要额外申请一个数组来保存变量。
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
int[] dist = new int[n];
for (int i = 0; i < n; i++) dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
for (int i = 0; i <= K; i++) {
for (int[] edge : flights) {
int u = edge[0];
int v = edge[1];
int w = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
}
}
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
Within K stops 最短路径 Cheapest Flights Within K Stops
原文：https://www.cnblogs.com/TIMHY/p/9678134.html