Skip to content

Instantly share code, notes, and snippets.

@cmattey
Last active Aug 28, 2019
Embed
What would you like to do?
from collections import defaultdict
import heapq
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
flight_map = defaultdict(list)
for start, end, price in flights:
flight_map[start].append([end,price])
heap = [(0, -1, src)] #price, stops, city
while heap:
cur_price, stops, cur_city = heapq.heappop(heap) # pop from heap
for neighbor, price in flight_map[cur_city]:
heapq.heappush(heap, (cur_price+price, stops+1, neighbor)) # push to heap
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment