> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/787-cheapest-flights-within-k-stops.md).

# 787     Cheapest Flights Within K Stops

## 787. [Cheapest Flights Within K Stops](https://leetcode.com/problems/cheapest-flights-within-k-stops/description/)

## 1. Question

There are`n`cities connected by `m`flights. Each fight starts from city `u`and arrives at `v`with a price`w`.

Now given all the cities and fights, together with starting city`src`and the destination `dst`, your task is to find the cheapest price from`src`to`dst`with up to`k`stops. If there is no such route, output`-1`.

```
Example 1:

Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1

Output: 200

Explanation:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
```

```
Example 2:

Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0

Output: 500

Explanation:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
```

## 2. Implementation

(1) Breadth First Search

思路:

```java
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        Map<Integer, List<int[]>> adjList = new HashMap();

        for (int[] flight : flights) {
            int fromCity = flight[0];
            int toCity = flight[1];
            int price = flight[2];
            adjList.putIfAbsent(fromCity, new ArrayList());
            adjList.get(fromCity).add(new int[] {toCity, price});
        }


        PriorityQueue<int[]> minHeap = new PriorityQueue<int[]>(new Comparator<int[]>() {
           @Override
            public int compare(int[] a, int[] b) {
                return a[2] - b[2];
            }
        });
        minHeap.add(new int[] {src, 0, 0});

        while (!minHeap.isEmpty()) {
            int[] curInfo = minHeap.remove();
            int curStop = curInfo[0];
            // 到达当前的stops 我们已经转了多少个stop
            int stops = curInfo[1];
            int curCost = curInfo[2];

            if (curStop == dst) {
                return curCost;
            }

            // 只有到达curStop时，转过的stops小于等于K时，我们才继续搜索
            if (stops <= K && adjList.containsKey(curStop)) {
                for (int[] nextInfo : adjList.get(curStop)) {
                    int nextStop = nextInfo[0];
                    int price = nextInfo[1];
                    minHeap.add(new int[] {nextStop, stops + 1, curCost + price});
                }
            }

        }
        return -1;
    }
}
```

## 3. Time & Space Complexity