[알고리즘] K 경유지 내 가장 저렴한 항공권

K 경유지 내 가장 저렴한 항공권

책 풀이

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    graph = collections.defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))

    Q = [(0, src, K)]

    while Q:
        price, node, k = heapq.heappop(Q)
        if node == dst:
            return price
        if k >= 0:
            for v, w in graph[node]:
                alt = price + w
                heapq.heappush(Q, (alt, v, k-1))
    return -1

K만큼 걸쳐서 갈 수 있으므로, 애초에 K를 주고 한번 이동할 때마다 하나씩 깎는다.