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

---

1. 전체 코드

import heapq
from collections import defaultdict


class Solution:
    def findCheapestPrice(self, n, flights, src, dst, K) -> int:
        graph = defaultdict(list)
        visited = defaultdict(int)
        for u, v, w in flights:
            graph[u].append((v, w))
        k = 0  # 경유 횟수
        h = [(0, src, k)]
        while h:
            price, node, k = heapq.heappop(h)
            if node == dst:
                return price

            # 어떤 노드를 다시 방문할 경우, 
            # 어떤 노드가 기존에 가졌던 경유 횟수보다 작아야 싸이클이 생성되지 않는다.
            if node not in visited or visited[node] > k:
                visited[node] = k  # 이 노드는 k 번의 경유로 도착함
                for v, w in graph[node]:
                    if k <= K:
                        alt = price + w
                        heapq.heappush(h, (alt, v, k + 1))

s = Solution()
print(s.findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0))

---

2. 후기

            # 어떤 노드를 다시 방문할 경우, 
            # 어떤 노드가 기존에 가졌던 경유 횟수보다 작아야 싸이클이 생성되지 않는다.
            if node not in visited or visited[node] > k:

1. 0, 1, 0  = heaq.heappop(h)
2. visited[1] = 0
3. heapq.heappush(h, (30, 2, 1))
4. 30, 2, 1  = heaq.heappop(h)

5. if visited[1](=0) > k(=1) -> if문 진입 불가