題目

https://leetcode.com/problems/cheapest-flights-within-k-stops/

題解

這題挺坑的實(shí)際上。DFS 超時(shí)了，因?yàn)樯婕暗讲綌?shù)限制 k，所以并不能加緩存，然后去看了答案。
答案給了一種 BFS 解法，看完思路我就開始一頓寫。

一開始是按照如果走回頭路的開銷比不走回頭路更小的話，就走回頭路這種思路來寫的。提交的時(shí)候發(fā)現(xiàn)，能不能走回頭路，這個(gè)問題會(huì)比較復(fù)雜。
回頭路是可以走的，但是不能簡單的用回頭路的開銷去覆蓋原有的開銷，因?yàn)樵谀阕呋仡^路的時(shí)候，3步到①可能比2步到①的實(shí)際開銷更小，但你不能確定在之后剩余的步數(shù)中，哪種選擇更好。

說白了就是，當(dāng)你還不能確定要不要走重復(fù)路線的時(shí)候，一維的dist不能同時(shí)保存走或不走兩種結(jié)果。
所以后來用了 int[2] 存儲(chǔ)[i，從src到i的距離。詳見注釋吧。

最后，貼一下混亂的草稿。

class Solution {public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {int[][] graph = new int[n][n];for (int i = 0; i < n; i++) {Arrays.fill(graph[i], -1);}for (int[] f : flights) {graph[f[0]][f[1]] = f[2];}// BFSint[] dist = new int[n]; // dist[i]表示src->i的距離Arrays.fill(dist, Integer.MAX_VALUE);dist[src] = 0;// 此處使用int[]的原因是，不能簡單的從dist中拿最小結(jié)果，因?yàn)樵谀阕呋仡^路的時(shí)候，3步到①可能比2步到①的實(shí)際開銷更小，// 但你不能確定在之后剩余的步數(shù)中，哪種選擇更好。// 說白了就是，當(dāng)你還不能確定要不要走重復(fù)路線的時(shí)候，一維的dist不能同時(shí)保存走或不走兩種結(jié)果。Stack<int[]> stack = new Stack<>(); // [i，從src到i的距離]。stack.push(new int[]{src, 0});int step = 0;while (step++ <= k) {if (stack.isEmpty()) break;Stack<int[]> newStack = new Stack<>();while (!stack.isEmpty()) {int[] pair = stack.pop(); // pair = [i，從src到i的距離]int i = pair[0];for (int j = 0; j < n; j++) { // src->i->j// 如果之前已經(jīng)走過，只有當(dāng)距離比原來小的時(shí)候才加入計(jì)算// 如果之前沒走過，則當(dāng)前距離肯定比INF小，所以肯定會(huì)加入計(jì)算if (i != j && graph[i][j] >= 0 && pair[1] + graph[i][j] < dist[j]) { dist[j] = pair[1] + graph[i][j];newStack.add(new int[]{j, dist[j]});}}}stack = newStack;}return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 787. Cheapest Flights Within K Stops | 787. K 站中转内最便宜的航班（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。