cheapest_flights_within_k_stops
1from collections import defaultdict 2from heapq import heappush, heappop 3 4 5# @leet start 6class Solution: 7 def findCheapestPrice( 8 self, n: int, flights: list[list[int]], src: int, dst: int, k: int 9 ) -> int: 10 """ 11 This is a Dijkstra's algorithm problem. 12 We start off with some starting node, src, and put that into our 13 heap with having 0 cost, 0 stops, and the id of the flight. 14 15 Then, for each node in the heap, we pop from the top the minimum 16 cost node, and check if we've made it to the destination in less 17 stops than allowed. 18 19 Otherwise, if we haven't visited this current node, or if we've 20 gotten to the node in fewer stops, we say we've visited this node 21 with a minimum cost of curr_stops, and then we push each of the neighbors 22 of the current node to the heap. 23 24 If we've gone through the entire heap and cannot make it at any cost 25 we return -1. 26 The time complexity is $O(n + E * K * log(E * K)$ 27 The space complexity is $O(N + E * K)$ 28 """ 29 visited = {} 30 adj = defaultdict(list) 31 32 for start, dest, price in flights: 33 adj[start].append((price, dest)) 34 35 heap = [(0, 0, src)] 36 while heap: 37 cost, stops, node = heappop(heap) 38 if node == dst and stops <= k + 1: 39 return cost 40 if node not in visited or visited[node] > stops: 41 visited[node] = stops 42 for price, neighbor in adj[node]: 43 heappush(heap, (cost + price, stops + 1, neighbor)) 44 return -1 45 46 47# @leet end 48 49 50def test(): 51 assert 2 + 2 == 4
class
Solution:
7class Solution: 8 def findCheapestPrice( 9 self, n: int, flights: list[list[int]], src: int, dst: int, k: int 10 ) -> int: 11 """ 12 This is a Dijkstra's algorithm problem. 13 We start off with some starting node, src, and put that into our 14 heap with having 0 cost, 0 stops, and the id of the flight. 15 16 Then, for each node in the heap, we pop from the top the minimum 17 cost node, and check if we've made it to the destination in less 18 stops than allowed. 19 20 Otherwise, if we haven't visited this current node, or if we've 21 gotten to the node in fewer stops, we say we've visited this node 22 with a minimum cost of curr_stops, and then we push each of the neighbors 23 of the current node to the heap. 24 25 If we've gone through the entire heap and cannot make it at any cost 26 we return -1. 27 The time complexity is $O(n + E * K * log(E * K)$ 28 The space complexity is $O(N + E * K)$ 29 """ 30 visited = {} 31 adj = defaultdict(list) 32 33 for start, dest, price in flights: 34 adj[start].append((price, dest)) 35 36 heap = [(0, 0, src)] 37 while heap: 38 cost, stops, node = heappop(heap) 39 if node == dst and stops <= k + 1: 40 return cost 41 if node not in visited or visited[node] > stops: 42 visited[node] = stops 43 for price, neighbor in adj[node]: 44 heappush(heap, (cost + price, stops + 1, neighbor)) 45 return -1
def
findCheapestPrice( self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
8 def findCheapestPrice( 9 self, n: int, flights: list[list[int]], src: int, dst: int, k: int 10 ) -> int: 11 """ 12 This is a Dijkstra's algorithm problem. 13 We start off with some starting node, src, and put that into our 14 heap with having 0 cost, 0 stops, and the id of the flight. 15 16 Then, for each node in the heap, we pop from the top the minimum 17 cost node, and check if we've made it to the destination in less 18 stops than allowed. 19 20 Otherwise, if we haven't visited this current node, or if we've 21 gotten to the node in fewer stops, we say we've visited this node 22 with a minimum cost of curr_stops, and then we push each of the neighbors 23 of the current node to the heap. 24 25 If we've gone through the entire heap and cannot make it at any cost 26 we return -1. 27 The time complexity is $O(n + E * K * log(E * K)$ 28 The space complexity is $O(N + E * K)$ 29 """ 30 visited = {} 31 adj = defaultdict(list) 32 33 for start, dest, price in flights: 34 adj[start].append((price, dest)) 35 36 heap = [(0, 0, src)] 37 while heap: 38 cost, stops, node = heappop(heap) 39 if node == dst and stops <= k + 1: 40 return cost 41 if node not in visited or visited[node] > stops: 42 visited[node] = stops 43 for price, neighbor in adj[node]: 44 heappush(heap, (cost + price, stops + 1, neighbor)) 45 return -1
This is a Dijkstra's algorithm problem. We start off with some starting node, src, and put that into our heap with having 0 cost, 0 stops, and the id of the flight.
Then, for each node in the heap, we pop from the top the minimum cost node, and check if we've made it to the destination in less stops than allowed.
Otherwise, if we haven't visited this current node, or if we've gotten to the node in fewer stops, we say we've visited this node with a minimum cost of curr_stops, and then we push each of the neighbors of the current node to the heap.
If we've gone through the entire heap and cannot make it at any cost we return -1. The time complexity is $O(n + E * K * log(E * K)$ The space complexity is $O(N + E * K)$
def
test():