Cheapest Flights Within K Stops

Solving tips

Shortest path with a 'at most k stops' budget means plain Dijkstra fails, because the cheapest way into a city may use too many edges to continue.
Reframe 'k stops' as 'k+1 edges' and run exactly k+1 rounds of Bellman-Ford, reading the cost at dst.
Critical pitfall: relax each round against a snapshot (copy) of the previous distances, or a single round chains multiple edges and overshoots the budget.
Target O(k*E) time and O(n) space; alternatively expand Dijkstra's state to (city, edges-used).

Problem

There are n cities numbered 0 to n - 1, connected by directed flights. Each flight is given as [u, v, price]: you can fly from city u to city v for price dollars.

Given a start city src, a destination dst, and an integer k, return the cheapest total price to travel from src to dst using at most k intermediate stops — i.e. a route of at most k + 1 flights. If no such route exists, return -1.

The catch: the globally cheapest route may use too many stops, so plain shortest-path logic is not enough.

Examples

n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 → 700 — the cheaper route 0→1→2→3 (cost 400) needs 2 stops, so we must take 0→1→3.
Same graph with k = 2 → 400 — now 0→1→2→3 is allowed.
n = 3, flights = [[0,1,100],[1,2,100]], src = 0, dst = 2, k = 0 → -1 — reaching city 2 requires stopping at city 1.

Constraints

1 <= n <= 100
0 <= len(flights) <= n * (n - 1), no duplicate edges
1 <= price <= 10^4
0 <= k < n, src != dst

Think about it first

Hint 1

"At most k stops" means "at most k + 1 edges". Rephrase the question as: what is the cheapest path from src to dst that uses at most k + 1 edges?

Hint 2

Why does ordinary Dijkstra fail here? Because the cheapest way to reach an intermediate city may burn too many edges to continue to dst. You need to track cost per number of edges used, not just per city.

Hint 3

Bellman-Ford relaxes every edge once per round, and after r rounds it has found the cheapest paths using at most r edges. Run exactly k + 1 rounds — relaxing against a snapshot of the previous round so a single round can't chain two new edges — and read off the answer at dst.

TL;DR

Bellman-Ford limited to k + 1 relaxation rounds — O(k · E) time, O(n) space.

Approach 1 — Brute force (DFS over all routes)

Try every route from src that uses at most k + 1 flights, tracking the running cost and keeping the best price that reaches dst. Pruning when the running cost already exceeds the best found keeps it from looping forever (prices are positive).

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

        best = [float("inf")]

        def dfs(node: int, edges_left: int, cost: int) -> None:
            if cost >= best[0]:
                return
            if node == dst:
                best[0] = cost
                return
            if edges_left == 0:
                return
            for nxt, price in adj[node]:
                dfs(nxt, edges_left - 1, cost + price)

        dfs(src, k + 1, 0)
        return -1 if best[0] == float("inf") else best[0]

Complexity: worst case O(n^(k+1)) time (branching factor up to n, depth k + 1), O(k) recursion space. With n = 100 and k up to 99, the route count explodes — the constraints kill it.

Approach 2 — Bellman-Ford, capped at k + 1 rounds

The insight: Bellman-Ford (the classic dynamic-programming shortest-path algorithm that relaxes every edge once per round) has an invariant tailor-made for this problem: after r rounds, dist[v] holds the cheapest cost to reach v using at most r edges. “At most k stops” is exactly “at most k + 1 edges” — so run precisely k + 1 rounds and stop. One subtlety: within a round, relax against a snapshot of the previous round’s distances, otherwise one round could chain several new edges together and overshoot the edge budget.

class Solution:
    def findCheapestPrice(self, n: int, flights: list[list[int]],
                          src: int, dst: int, k: int) -> int:
        INF = float("inf")
        dist = [INF] * n
        dist[src] = 0
        for _ in range(k + 1):
            prev = dist[:]
            for u, v, price in flights:
                if prev[u] + price < dist[v]:
                    dist[v] = prev[u] + price
        return -1 if dist[dst] == INF else dist[dst]

Walkthrough (n = 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1):

Start: dist = [0, INF, INF, INF].
Round 1 (snapshot [0, INF, INF, INF]): only edge 0→1 has a finite source, so dist = [0, 100, INF, INF].
Round 2 (snapshot [0, 100, INF, INF]): 1→2 gives dist[2] = 200; 1→3 gives dist[3] = 700. dist = [0, 100, 200, 700].
Two rounds = at most 2 flights = at most 1 stop. Answer: dist[3] = 700. The 400-cost route through city 2 needs a third flight, and the snapshot discipline correctly kept it out.

Complexity: O(k · E) time, O(n) space.

Approach 3 — Dijkstra on (city, edges-used) states

The insight: ordinary Dijkstra (greedy shortest-path: always settle the unvisited node with the smallest known distance, using a min-heap) breaks here because the cheapest way into a city may have burned too many edges. Fix it by making the state richer: run Dijkstra over pairs (city, edges used). The first time we pop dst its cost is optimal, because heap order is by cost. To prune, skip a state if we’ve already reached this city using fewer edges — any route through it would have been found cheaper-or-equal already.

import heapq

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

        best_edges = [float("inf")] * n
        heap = [(0, 0, src)]  # (cost, edges used, city)
        while heap:
            cost, edges, node = heapq.heappop(heap)
            if node == dst:
                return cost
            if edges > k or edges >= best_edges[node]:
                continue
            best_edges[node] = edges
            for nxt, price in adj[node]:
                heapq.heappush(heap, (cost + price, edges + 1, nxt))
        return -1

Walkthrough (same example, k = 1): pop (0, 0, 0), push (100, 1, 1). Pop (100, 1, 1), push (200, 2, 2) and (700, 2, 3). Pop (200, 2, 2): edges = 2 > k, skip — city 2 is a dead end under this budget. Pop (700, 2, 3): it’s dst, return 700.

Complexity: each city can enter the heap once per edge count, so O(E · k) heap entries → O(E · k · log(E · k)) time, O(E · k) space. Fine here, but note Bellman-Ford is both simpler and asymptotically better for this problem.

Common pitfalls

Relaxing against the live dist array instead of a snapshot — one Bellman-Ford round then chains multiple edges and violates the stop budget.
Confusing stops with edges: k stops means k + 1 flights, so the loop runs k + 1 times.
Using plain Dijkstra with a per-city visited set — it discards more-expensive-but-fewer-edges routes that are the only legal way to reach dst.
Forgetting the unreachable case: return -1 when dst still holds infinity.

Pattern takeaway

When a shortest-path problem adds a budget (edge count, stops, fuel), the plain node-distance table is no longer a valid state space. Either bound the rounds of Bellman-Ford (each round = one more edge allowed) or expand Dijkstra’s state to (node, budget used). Bellman-Ford’s round-by-round invariant is the cleanest tool whenever the budget is on the number of edges.