作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
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:
有N个城市,m个航班,他们之间的连接是个有向图。现在已知最多可以中转k次,求从srt到dst的最小花费。
图的遍历的基础上加上了一个限制条件:最多中转k次,即最多只能访问k+1个节点。可以用DFS和BFS两者方法去解决。
这个其实就是回溯法,先从起点开始向后搜索,如果搜索到了dst或者没有步数了,那么换下一条路进行搜索。需要使用一个visited数组表示已经搜索过的节点,这样可以防止走成一个环。
另外这个题需要一个强剪枝,就是当某条路径的花费大于了我们当前到达dst需要花费的最小值的时候,后面的路径都不需要走了,这个是由于题目给出的路费都是整数,向下走哪怕走到了dst花费也会更高。
时间复杂度是O(N^2),空间复杂度是O(1).打败了6%的提交。
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,这样就可以直接判断在指定的k步以内能不能走到dst,不会进行更多的搜索了,因此这个方法要快很多。
BFS是个模板,直接使用一个队列很容易就实现了。这个队列存放的是当我们进行第step次搜索时,搜索到的当前的节点,以及走到当前节点的花费。所以当当前节点走到dst时,更新最小花费。
时间复杂度是O(KN),空间复杂度是O(N).打败了60%的提交。
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
https://www.youtube.com/watch?v=PLY-lbcxEjg
2018 年 10 月 23 日 —— 风真是个好东西
手机扫一扫
移动阅读更方便
你可能感兴趣的文章