# 787. Cheapest Flights Within K Stops K 站中转内最便宜的航班

@TOC

## # 题目描述

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 flights, 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.

## # 解题方法

### # 方法一：DFS

``````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
"""
graph = collections.defaultdict(dict)
for u, v, e in flights:
graph[u][v] = e
visited = [0] * n
ans = [float('inf')]
self.dfs(graph, src, dst, K + 1, 0, visited, ans)
return -1 if ans[0] == float('inf') else ans[0]

def dfs(self, graph, src, dst, k, cost, visited, ans):
if src == dst:
ans[0] = cost
return
if k == 0:
return
for v, e in graph[src].items():
if visited[v]: continue
if cost + e > ans[0]: continue
visited[v] = 1
self.dfs(graph, v, dst, k - 1, cost + e, visited, ans)
visited[v] = 0
``````

### # 方法二：BFS

BFS是个模板，直接使用一个队列很容易就实现了。这个队列存放的是当我们进行第step次搜索时，搜索到的当前的节点，以及走到当前节点的花费。所以当当前节点走到dst时，更新最小花费。

``````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
"""
graph = collections.defaultdict(dict)
for u, v, e in flights:
graph[u][v] = e
ans = float('inf')
que = collections.deque()
que.append((src, 0))
step = 0
while que:
size = len(que)
for i in range(size):
cur, cost = que.popleft()
if cur == dst:
ans = min(ans, cost)
for v, w in graph[cur].items():
if cost + w > ans:
continue
que.append((v, cost + w))
if step > K: break
step += 1
return -1 if ans == float('inf') else ans
``````

## # 日期

2018 年 10 月 23 日 —— 风真是个好东西