Cheapest Flights Within K Stops

lcpy gen -n 787   # by problem number
lcpy gen -s cheapest_flights_within_k_stops   # by problem name

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation:
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.

from collections import deque


class Solution:
    # Time: O(K * E) where E is number of flights
    # Space: O(V) where V is number of cities
    def find_cheapest_price(
        self, n: int, flights: list[list[int]], src: int, dst: int, k: int
    ) -> int:
        # Build adjacency list
        adj = [[] for _ in range(n)]
        for from_i, to_i, price_i in flights:
            adj[from_i].append((to_i, price_i))

        # BFS with stops constraint
        prices = [float("inf")] * n
        prices[src] = 0
        queue = deque([(src, 0, 0)])  # (node, current_price, stops)

        while queue:
            node, current_price, stops = queue.popleft()
            if stops > k:
                continue
            for neighbor, price in adj[node]:
                new_price = current_price + price
                if new_price < prices[neighbor]:
                    prices[neighbor] = new_price
                    queue.append((neighbor, new_price, stops + 1))

        return int(prices[dst]) if prices[dst] != float("inf") else -1