CheapestTicketPrice.py

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)
		
		if stops>k:
			continue
			
		if cur_city==dst:
			return cur_price
		
		for neighbor, price in flight_map[cur_city]:
			heapq.heappush(heap, (cur_price+price, stops+1, neighbor))
			
	return -1