787. Cheapest Flights Within K Stops

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

 

 

Bellman-Ford로 푸는게 가장 간단하다고 한다?

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        """Bellman-Ford"""
        INF = 10**15
        dist = [INF] * n
        dist[src] = 0

        for _ in range(k + 1):
            tmp = dist[:]  # use snapshot
            for u, v, w in flights:
                if dist[u] == INF:
                    continue
                if dist[u] + w < tmp[v]:
                    tmp[v] = dist[u] + w
            dist = tmp

        return -1 if dist[dst] == INF else dist[dst]

 

Dijkstra로 푸는 방법은 그냥 찾아봤다.

 

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        """Dijkstra"""
        # 인접 리스트 구성
        adj = [[] for _ in range(n)]
        for u, v, w in flights:
            adj[u].append((v, w))

        INF = 10**15
        max_edges = K + 1  # 정지 K번 => 간선은 최대 K+1개
        # dist[node][edges_used] = edges_used개 간선을 써서 node에 도달하는 최소 비용
        dist = [[INF] * (max_edges + 1) for _ in range(n)]
        dist[src][0] = 0

        # 간단한 우선순위 큐: 리스트에 넣고, 매번 최소 cost를 선형 탐색으로 꺼냄
        pq = [(0, src, 0)]  # (cost, node, edges_used)

        def pop_min(q):
            mi = 0
            for i in range(1, len(q)):
                if q[i][0] < q[mi][0]:
                    mi = i
            return q.pop(mi)

        while pq:
            cost, u, e = pop_min(pq)
            if u == dst:
                return cost  # 제약 하에서 최소 비용

            # 이미 더 좋은 경로가 기록돼 있으면 스킵
            if cost > dist[u][e]:
                continue

            # 간선 제한 체크
            if e == max_edges:
                continue

            ne = e + 1
            for v, w in adj[u]:
                nc = cost + w
                if nc < dist[v][ne]:
                    dist[v][ne] = nc
                    pq.append((nc, v, ne))

        ans = min(dist[dst])
        return -1 if ans == INF else ans