## 题目描述：

LeetCode 787. Cheapest Flights Within K Stops

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 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:

• 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.

## 解题思路：

`ans = min(ans, costs[k] + prices[k][dst])`

​其中costs[k]表示到达位置k时的最小花费，prices[k][dst]表示从k到达dst的航班价格。

## Python代码：

``````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
"""
INF = 0x7FFFFFFF
prices = collections.defaultdict(lambda: collections.defaultdict(int))
for s, t, p in flights:
prices[s][t] = p
ans = prices[src][dst] or INF
queue = [src]
costs = {src : 0}
for x in range(K + 1):
nset = set()
for loc in queue:
ans = min(ans, costs[loc] + (prices[loc][dst] or INF))
for next in prices[loc]:
costs[next] = min(costs.get(next, INF), costs[loc] + (prices[loc][next] or INF))
queue = list(nset)
return ans if ans < INF else -1
``````

Pingbacks已关闭。