Learning On the Way

787. Cheapest Flights Within K Stops

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return-1

def findCheapestPrice(self, n, flights, src, dst, K): 
    graph = defaultdict(list) 
    for s, d, p in flights: 
        graph[s].append((d, p))

    least_moves = defaultdict(lambda: float('inf')) 
    least_cost = defaultdict(lambda: float('inf')) 
    least_moves[src] = 0 
    least_cost[src] = 0

    # price, moves, node 
    heap = [(0, 0, src)] 
    while heap: 
        price, moves, node = heappop(heap) 
        if node == dst: 
            return price 
        if moves == K + 1:  # No remaining stops to use 
            continue 
        new_moves = moves + 1

        for nei, cost in graph[node]: 
            new_prive = price + cost 
            if new_prive < least_cost[nei] or new_moves < least_moves[nei]:  # Need to be better on either dimension; actually we want the new entry to be better than all previous entries in at least one dimension, but it will take time to implement it. So here simply record the lastest entry for the same destination and compare the new entry with it as a method for pruning
                least_cost[nei] = new_price 
                least_moves[nei] = new_moves 
                heappush(heap, (new_price, new_moves, nei))

    return -1