[LeetCode] 787. Cheapest Flights Within K Stops

- Problem

787. Cheapest Flights Within K Stops

- 내 풀이

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:    
        def dijkstra():
            heap = [(0, src, k)]
            visited = set()
            visited.add(heap[0])

            while heap:
                cur_cost, cur_node, cnt = heappop(heap)
                if cur_node == dst:
                    return cur_cost

                for nxt_cost, nxt_node in graph[cur_node]:
                    visit_status = (cur_cost + nxt_cost, nxt_node ,cnt - 1)
                    if cnt > -1 and visit_status not in visited:
                        visited.add(visit_status)
                        heappush(heap, visit_status)
            
            return -1

        graph = defaultdict(list)

        for x, y, price in flights:
            graph[x].append((price, y))

        return dijkstra()

- 결과