Cheapest Flights Within K Stops

Intuition

This is a shortest-path problem with an extra constraint: the number of edges (stops) is bounded. Plain Dijkstra can settle a node too early with a cheap-but-stop-heavy path and then miss a pricier route that still has budget to reach the destination. So instead of finalizing nodes by cost alone, we carry the remaining stop budget inside each heap state and allow a node to be revisited when we arrive with more budget to spend. Because the heap pops by cost, the first time the destination comes off the heap its cost is the minimum achievable within the limit. A classic alternative is Bellman-Ford restricted to k + 1 relaxation rounds, which also honors the stop bound without a heap.

Algorithm walkthrough

1. 1Build an adjacency list of outgoing flights (to, price) for every city.
2. 2Seed a min-heap keyed on total cost with (0, src, k), where the third field is the remaining stop budget.
3. 3Pop the cheapest state; if its node is dst, that cost is optimal under the budget, so return it.
4. 4Skip the state if its budget is negative, or if this node was already expanded with an equal-or-larger budget (a dominated state).
5. 5Otherwise record the budget for this node and push each neighbor with cost + price and budget - 1.
6. 6If the heap empties without reaching dst, no route exists within k stops, so return -1.

Implementation

import heapq
from typing import List


class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        graph = [[] for _ in range(n)]
        for u, v, w in flights:
            graph[u].append((v, w))

        best = [-1] * n            # best[node] = max stop-budget seen when expanded
        heap = [(0, src, k)]       # (cost, node, stops_remaining)

        while heap:
            cost, node, stops = heapq.heappop(heap)
            if node == dst:
                return cost
            if stops < 0 or stops <= best[node]:
                continue
            best[node] = stops
            for nei, w in graph[node]:
                heapq.heappush(heap, (cost + w, nei, stops - 1))

        return -1