787. Cheapest Flights Within K Stops

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

Python

BFS DP

from math import inf
from collections import deque, defaultdict


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        mapper = defaultdict(lambda: defaultdict(lambda: inf))

        for source, dest, price in flights:
            mapper[source][dest] = min(price, mapper[source][dest])

        dp = [inf for _ in range(n)]
        dp[src] = 0

        queue = deque([(0, src, 0)])

        path = set([src])
        while queue:
            cost, current, stops = queue.popleft()
            dp[current] = min(dp[current], cost)
            for cand_dst in mapper[current]:
                if stops > k:
                    continue
                if dp[current] + mapper[current][cand_dst] < dp[cand_dst]:
                    queue.append(
                        (dp[current]+mapper[current][cand_dst], cand_dst, stops+1)
                    )

        return dp[dst] if dp[dst] != inf else -1

Dijkstra

(TODO)