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