2023.01.26 Today's Challenge

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

Cheapest Flights Within K Stops - LeetCode

priority queue (우선 순위 큐)를 활용하면 DFS 를 쓰는 것보다 좀 더 간단히 풀 수 있음.

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        graph = [[] for _ in range(n)]
        min_heap = [(0, src, k+1)]
        dist = [[math.inf] * (k+2) for _ in range(n)]

        for u, v, w in flights:
            graph[u].append((v, w))

        while min_heap:
            d, u, stops = heapq.heappop(min_heap)            
            if u == dst:
                return d            
            if stops > 0:
                for v, w in graph[u]:
                    new_dist = d + w
                    if new_dist < dist[v][stops - 1]:
                        dist[v][stops - 1] = new_dist
                        heapq.heappush(min_heap, (new_dist, v, stops - 1))
        
        return -1