Loading... # 问题 [LeetCode #787](https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/) 在单源最短路径问题的基础上，加一条限制，最多只能通过K个点中转，或说最多只能通过K+1条边。 # 解决 除了Dijkstra之外，还有一个单源最短路径算法，叫做Bellman-Ford算法。离散教材上用它来解决带有负权边的单源最短路径问题。事实上，它也可以解决这种限制了最多中转次数的问题。 Bellman-Ford算法的原型在此不做赘述了，其核心就是迭代，没迭代一次相当于从源点向外走了一步，有一点像BFS。而这个过程略作改造就可以解决本问题。原型核心代码如下： ```cpp while (true) { bool changed = 0; for (int i = 0; i < n; i++) { // j -> i for (int j = 0; j < n; j++) { if (graph[j][i] < inf && ans[i] > bak_ans[j] + graph[j][i]) { ans[i] = bak_ans[j] + graph[j][i]; changed = 1; } } } if (!changed) break; } ``` 为什么要改造呢？因为我们现在要求每一步迭代（即while中的部分）只能走一步。而假想一个图，1->2，2->3，1->3，求1->3的单源最短路径，第一次迭代中，ans[2]被更新（相当于从1到2），紧接着ans[3]借着刚刚更新的ans[2]被更新（相当于从2到3），即这一次迭代中走了两步。（如果1->3的距离大于1->2加2->3的距离，那么第一次迭代之后保留的就是后者。）如果是这样的话，我们就没法通过控制迭代次数来控制最多走多少边了。因此，我们不能让ans[3]更新时享用同一次迭代中ans[2]刚刚更新的数值，而只能让它用上一轮迭代后的数值，这样一次迭代就只能走一步了。 于是，只要做一个数据分离就可以解决一次迭代走多步的问题了。修改后（把while循环改成了对k的循环），很容易得到完整的代码如下，实现了最多走K+1条边，或说最多通过K个点转移的效果。 ```cpp class Solution { public: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { // bellman-ford int graph[100][100] = { 0 }; memset(graph, 0x3f, sizeof(graph)); const int inf = 60000000; for (auto iter : flights) { graph[iter[0]][iter[1]] = iter[2]; } int ans[100] = { 0 }; memset(ans, 0x3f, sizeof(ans)); ans[src] = 0; for (int k = 1; k <= K + 1; k++) { bool changed = 0; int bak_ans[100] = { 0 }; for (int i = 0; i < n; i++) bak_ans[i] = ans[i]; for (int i = 0; i < n; i++) { // j -> i for (int j = 0; j < n; j++) { if (graph[j][i] < inf && ans[i] > bak_ans[j] + graph[j][i]) { ans[i] = bak_ans[j] + graph[j][i]; changed = 1; } } } if (!changed) break; } int res = ans[dst] < inf ? ans[dst] : -1; return res; } }; ``` Last modification：June 24th, 2020 at 03:52 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author