SHARE
TWEET

Untitled

a guest Aug 20th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import defaultdict
  2. import heapq
  3.  
  4. def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
  5.  
  6.     flight_map = defaultdict(list)
  7.    
  8.     for start, end, price in flights:
  9.        
  10.         fligh_map[start].append([end,price])
  11.        
  12.     heap = [(0, -1, src)] #price, stops, city
  13.    
  14.     while heap:
  15.        
  16.         cur_price, stops, cur_city = heapq.heappop(heap)
  17.        
  18.         if stops>k:
  19.             continue
  20.            
  21.         if cur_city==dst:
  22.             return cur_price
  23.        
  24.         for neighbor, price in flight_map[cur_city]:
  25.             heapq.heappush(heap, (cur_price+price, stops+1, neighbor))
  26.            
  27.     return -1
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top