787. Cheapest Flights Within K Stops

방문한거 안세주면 순환해서 방문한거 세줘야함.

import collections
import heapq

class Solution:
    def findCheapestPrice(self, n: int, flights, src: int, dst: int, k: int) -> int:
        graph = collections.defaultdict(list)

        # 입력값으로 그래프 만들어줌
        for departure, destination, price in flights:
            graph[departure].append([destination, price])

        # k가 출발점이니 자기자신으로 가는거는 시간이 0임 여기부터 시작해야함
        # 출발점에서 목적지까지의 시간, 목적지, 남은 경유횟수임
        # 초기 잔여 경유 횟수를 0으로 맞추기 위해서 k + 1로 시작함
        queue = [[0, src, k + 1]]

        # 방문지의 잔여 경유 횟수를 기록해줌
        vis = [0] * n
        while queue:
            # 힙에서 출발점에서 정점까지의 소요시간이 가장 작은 순서대로 빼줌
            cur_price, node, k = heapq.heappop(queue)

            # 도착점 찾았으면 비용 리턴해줌
            if node == dst:
                return cur_price

            # 노드에 방문 했는데 경유 횟수를 전부 소모했으면 세지말아야함
            if vis[node] >= k:
                continue
        
            # 잔여 경유 횟수 갱신해줌
            vis[node] = k
            for destination, price in graph[node]:
                # 다다음 정점까지의 거리는 출발점에서 다음정점까지의 거리 + 다음 정점에서 다다음 정점까지의 거리임
                # 출발점에서 목적지까지의 비용, 목적지, 목적지에 들어가는데 남은 경유 횟수
                heapq.heappush(queue, [cur_price + price, destination, k - 1])

        # 정답 찾으면 안에서 리턴해주니 다돌고 나오면 못찾은거임
        return -1

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