> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Cheapest Flights Within K Stops

> Tested Python solution for LeetCode 787 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 787, Medium. Topics: Dynamic Programming, Depth-First Search, Breadth-First Search, Graph Theory, Heap (Priority Queue), Shortest Path. [View on LeetCode](https://leetcode.com/problems/cheapest-flights-within-k-stops/description/).

Generate this problem as a practice environment: tested reference solution, 13 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 787   # by problem number
lcpy gen -s cheapest_flights_within_k_stops   # by problem name
```

## Problem

There are `n` cities connected by some number of flights. You are given an array `flights` where `flights[i] = [fromi, toi, pricei]` indicates that there is a flight from city `fromi` to city `toi` with cost `pricei`.

You are also given three integers `src`, `dst`, and `k`, return **the cheapest price** from `src` to `dst` with at most `k` stops. If there is no such route, return `-1`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png)

```
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.
```

![Example 2](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png)

```
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.
```

![Example 3](https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png)

```
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.
```

### Constraints

* 2 \<= n \<= 100
* 0 \<= flights.length \<= (n \* (n - 1) / 2)
* flights\[i].length == 3
* 0 \<= fromi, toi \< n
* fromi != toi
* 1 \<= pricei \<= 10^4
* There will not be any multiple flights between two cities.
* 0 \<= src, dst, k \< n
* src != dst

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/cheapest_flights_within_k_stops/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/cheapest_flights_within_k_stops/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
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
```

## Complexity

| Time                                   | Space                            |
| -------------------------------------- | -------------------------------- |
| O(K \* E) where E is number of flights | O(V) where V is number of cities |

## Tags

[Grind](/catalog/grind), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode), [AlgoMaster 75](/catalog/algo-master-75).