https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

787.cheapest_flights_within_K_stops2.py

# Time:  O(E+nlogn), where E is the length of flights
# Space: O(n), the size of the heap 
# Reference: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/

'''
# Dijkstra's algorithm 
If we continually extend our potential flightpaths in order of cost, we know once we've reached the destination dst that it was the lowest cost way to get there. 
'''
import collections
class Solution(object):
    def findCheapestPrice(self, n, flights, src, dst, K):
        """
        :type n: int
        :type flights: List[List[int]]
        :type src: int
        :type dst: int
        :type K: int
        :rtype: int
        """
        graph = collections.defaultdict(dict)
        for u, v, w in flights:
            graph[u][v] = w
        
        best = {} # the best way to get any point 
        pq =[(0, 0, src)] # cost A with B steps to get C
        while pq:
            cost, k, place = heapq.heappop(pq)
            if k > K+1 or cost > best.get((k, place), float('inf')): continue 
            if place == dst: return cost 
            
            for nei, wt in graph[place].iteritems():
                newcost = cost + wt 
                if newcost < best.get((k+1, nei), float('inf')):
                    heapq.heappush(pq, (newcost, k+1, nei))
                    best[k+1, nei] = newcost 
                    
        return -1