# [LeetCode] 787. Cheapest Flights Within K Stops K次起色内的最便宜航班

2021年09月15日 阅读数：2

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

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`.java

```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 graph looks like this:
```

`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 graph looks like this:
```

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

Note:node

• The number of nodes `n` will be in range `[1, 100]`, with nodes labeled from `0` to `n`` - 1`.
• The size of `flights` will be in range `[0, n * (n - 1) / 2]`.
• The format of each flight will be `(src, ``dst``, price)`.
• The price of each flight will be in the range `[1, 10000]`.
• `k` is in the range of `[0, n - 1]`.
• There will not be any duplicated flights or self cycles.

Java:app

```class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
Map<Integer, Map<Integer, Integer>> prices = new HashMap<>();
for (int[] f : flights) {
if (!prices.containsKey(f[0])) prices.put(f[0], new HashMap<>());
prices.get(f[0]).put(f[1], f[2]);
}
Queue<int[]> pq = new PriorityQueue<>((a, b) -> (Integer.compare(a[0], b[0])));
pq.add(new int[] {0, src, k + 1});
while (!pq.isEmpty()) {
int[] top = pq.remove();
int price = top[0];
int city = top[1];
int stops = top[2];
if (city == dst) return price;
if (stops > 0) {
Map<Integer, Integer> adj = prices.getOrDefault(city, new HashMap<>());
for (int a : adj.keySet()) {
pq.add(new int[] {price + adj.get(a), a, stops - 1});
}
}
}
return -1;
}
}　```

Python:post

```class Solution(object):
def findCheapestPrice(self, n, flights, src, dst, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int
:rtype: int
"""
adj = collections.defaultdict(list)
for u, v, w in flights:
adj[u].append((v, w))
best = collections.defaultdict(lambda: collections.defaultdict(lambda: float("inf")))
min_heap = [(0, src, K+1)]
while min_heap:
result, u, k = heapq.heappop(min_heap)
if k < 0 or best[u][k] < result:
continue
if u == dst:
return result
for v, w in adj[u]:
if result+w < best[v][k-1]:
best[v][k-1] = result+w
heapq.heappush(min_heap, (result+w, v, k-1))
return -1
```

Python:this

```class Solution(object):
def findCheapestPrice(self, n, flights, src, dst, K):
"""
:type n: int
:type flights: List[List[int]]
:type src: int
:type dst: int
:type K: int
:rtype: int
"""
f = collections.defaultdict(dict)
for a, b, p in flights:
f[a][b] = p
heap = [(0, src, k + 1)]
while heap:
p, i, k = heapq.heappop(heap)
if i == dst:
return p
if k > 0:
for j in f[i]:
heapq.heappush(heap, (p + f[i][j], j, k - 1))
return -1　　```

C++:url

```// Time:  O((|E| + |V|) * log|V|) = O(|E| * log|V|)
// Space: O(|E| + |V|) = O(|E|)

class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
using P = pair<int, int>;
unordered_map<int, vector<P>> adj;
for (const auto& flight : flights) {
int u, v, w;
tie(u, v, w) = make_tuple(flight[0], flight[1], flight[2]);
adj[u].emplace_back(v, w);
}

unordered_map<int, unordered_map<int, int>> best;
using T = tuple<int, int, int>;
priority_queue<T, vector<T>, greater<T>> min_heap;
min_heap.emplace(0, src, K + 1);
while (!min_heap.empty()) {
int result, u, k;
tie(result, u, k) = min_heap.top(); min_heap.pop();
if (k < 0 ||
(best.count(u) && best[u].count(k) &&  best[u][k] < result)) {
continue;
}
if (u == dst) {
return result;
}
for (const auto& kvp : adj[u]) {
int v, w;
tie(v, w) = kvp;
if (!best.count(v) ||
!best[v].count(k - 1) ||
result + w < best[v][k - 1]) {
best[v][k - 1] = result + w;
min_heap.emplace(result + w, v, k - 1);
}
}
}
return -1;
}
};
```