forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcheapest-flights-within-k-stops.py
More file actions
68 lines (55 loc) · 1.97 KB
/
cheapest-flights-within-k-stops.py
File metadata and controls
68 lines (55 loc) · 1.97 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import heapq
import collections
"""
We start from src and only got K+1 stops to use
Each time, we choose the cheapest place to go.
If the city we popout is dst, then the price must be lowest
Since we always pick the lowest place to go.
If we still have stops left (stops>1), we put its neighbor to the priority queue.
So the city in the priority queue must be within the stops limit.
Making the graph takes O(E)
The size of priority queue is O(V), since we might put all the cities in it.
So for every pop, it is O(LogV). Total is O(VLogV).
For every edge we call an heappush, so that is ELogV
O(E+ (V+E)LogV) -> O((V+E)LogV)
V is the number of cities within range K stops.
"""
#Dijkstra
class Solution1(object):
def findCheapestPrice(self, n, flights, src, dst, K):
graph = collections.defaultdict(list)
pq = []
for u, v, w in flights: graph[u].append((w, v))
heapq.heappush(pq, (0, K+1, src))
while pq:
price, stops, city = heapq.heappop(pq)
if city is dst: return price
if stops>0:
for price_to_nei, nei in graph[city]:
heapq.heappush(pq, (price+price_to_nei, stops-1, nei))
return -1
"""
This is mostly straight forward BFS.
When we are out of stops, or price is greater than min_price, we stop adding cities to the queue.
Every time we encounter dst we compare the price and set it to the min.
Making the graph takes O(E)
BFS every node in adjacent list takes O(V+E)
V is the number of cities within range K stops.
"""
#BFS
class Solution2(object):
def findCheapestPrice(self, n, flights, src, dst, K):
graph = collections.defaultdict(list)
q = collections.deque()
min_price = float('inf')
for u, v, w in flights: graph[u].append((w, v))
q.append((src, 0, 0))
while q:
city, stops, price = q.popleft()
if city==dst:
min_price = min(min_price, price)
continue
if stops<=K and price<=min_price:
for price_to_nei, nei in graph[city]:
q.append((nei, stops+1, price+price_to_nei))
return min_price if min_price!=float('inf') else -1