# LeetCode 787: Cheapest Flights Within K Stops

## Problem Restatement

We are given `n` cities labeled from `0` to `n - 1`.

We are also given a list of directed flights. Each flight is represented as:

```python
[from_city, to_city, price]
```

We need to find the cheapest price to travel from `src` to `dst` using at most `k` stops.

A stop means an intermediate city between `src` and `dst`.

So at most `k` stops means at most `k + 1` flights.

If no such route exists, return `-1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `n`, `flights`, `src`, `dst`, and `k` |
| Output | Cheapest price from `src` to `dst` with at most `k` stops |
| Flight format | `[from_city, to_city, price]` |
| Graph type | Directed weighted graph |
| Stop limit | At most `k` intermediate cities |
| Flight limit | At most `k + 1` edges |

Function shape:

```python
class Solution:
    def findCheapestPrice(
        self,
        n: int,
        flights: list[list[int]],
        src: int,
        dst: int,
        k: int
    ) -> int:
        ...
```

## Examples

Example 1:

```python
n = 3
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
src = 0
dst = 2
k = 1
```

There are two relevant routes:

| Route | Stops | Cost |
|---|---:|---:|
| `0 -> 2` | `0` | `500` |
| `0 -> 1 -> 2` | `1` | `200` |

At most `1` stop is allowed, so the cheaper valid route is:

```text
0 -> 1 -> 2
```

The answer is:

```python
200
```

Example 2:

```python
n = 3
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
src = 0
dst = 2
k = 0
```

Now no intermediate stop is allowed.

The route `0 -> 1 -> 2` uses one stop, so it is invalid.

The only valid route is:

```text
0 -> 2
```

The answer is:

```python
500
```

## First Thought: Use Normal Shortest Path

This looks like a shortest path problem.

Each city is a node.

Each flight is a directed weighted edge.

A normal shortest path algorithm would try to minimize total price.

But here we also have a stop limit.

The cheapest path by price may use too many stops.

For example:

```text
0 -> 1 -> 2 -> 3
```

may be cheaper than:

```text
0 -> 1 -> 3
```

but if `k = 1`, then `0 -> 1 -> 2 -> 3` is invalid because it has two stops.

So we need to track both price and number of flights used.

## Key Insight

At most `k` stops means at most `k + 1` flights.

This suggests a bounded version of Bellman-Ford.

Bellman-Ford relaxes all edges repeatedly.

After one relaxation round, we know the cheapest prices using at most one flight.

After two rounds, we know the cheapest prices using at most two flights.

After `k + 1` rounds, we know the cheapest prices using at most `k + 1` flights.

That exactly matches the problem.

The important detail is that each round must use a copy of the previous distance array.

Without a copy, updates from the current round could be reused immediately, accidentally allowing too many flights in one round.

## Algorithm

Use `dist`, where:

```python
dist[city]
```

means the cheapest cost to reach `city` using the number of flights allowed so far.

Initialize:

```python
dist[src] = 0
```

All other cities start as infinity.

Then repeat `k + 1` times:

1. Copy the current distances into `next_dist`.
2. For every flight `(u, v, price)`:
   1. If `dist[u]` is reachable, try flying from `u` to `v`.
   2. Update `next_dist[v]`.
3. Replace `dist` with `next_dist`.

After the loop, if `dist[dst]` is still infinity, return `-1`.

Otherwise, return `dist[dst]`.

## Correctness

We prove that after `r` relaxation rounds, `dist[x]` is the cheapest cost to reach city `x` using at most `r` flights.

Before any relaxation, `dist[src] = 0` and all other cities are unreachable. This is correct for using at most `0` flights.

Assume the statement is true before round `r + 1`. During this round, every route using at most `r + 1` flights either already used at most `r` flights, or it is formed by taking a route with at most `r` flights to some city `u`, then one more flight from `u` to `v`.

The algorithm checks every flight `(u, v, price)` and updates `v` using the previous round distance to `u`. Therefore, it considers exactly all routes that can be formed with one additional flight.

Because the algorithm uses a copied array, a route cannot use two new flights during the same round. Thus, round `r + 1` represents at most `r + 1` flights, not more.

By induction, after `k + 1` rounds, `dist[dst]` is the cheapest cost to reach `dst` using at most `k + 1` flights, which is the same as at most `k` stops.

Therefore, the algorithm returns the correct answer.

## Complexity

Let `m = len(flights)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O((k + 1) * m)` | We scan every flight for each allowed flight count |
| Space | `O(n)` | We store distance arrays of length `n` |

Since `k < n`, the time can also be written as `O(nm)` in the worst case.

## Implementation

```python
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):
            next_dist = dist.copy()

            for start, end, price in flights:
                if dist[start] == inf:
                    continue

                next_dist[end] = min(
                    next_dist[end],
                    dist[start] + price
                )

            dist = next_dist

        if dist[dst] == inf:
            return -1

        return dist[dst]
```

## Code Explanation

We start with all cities unreachable:

```python
dist = [inf] * n
```

The source city costs `0` to reach:

```python
dist[src] = 0
```

We perform `k + 1` rounds because at most `k` stops means at most `k + 1` flights:

```python
for _ in range(k + 1):
```

At the start of each round, we copy the current distances:

```python
next_dist = dist.copy()
```

This preserves the boundary between routes using at most the previous number of flights and routes using one more flight.

Then we scan all flights:

```python
for start, end, price in flights:
```

If the start city is not reachable yet, this flight cannot help:

```python
if dist[start] == inf:
    continue
```

Otherwise, try using this flight:

```python
next_dist[end] = min(
    next_dist[end],
    dist[start] + price
)
```

After processing all flights, the next distances become current:

```python
dist = next_dist
```

Finally, return `-1` if the destination was never reached:

```python
if dist[dst] == inf:
    return -1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findCheapestPrice(
        3,
        [[0, 1, 100], [1, 2, 100], [0, 2, 500]],
        0,
        2,
        1,
    ) == 200

    assert s.findCheapestPrice(
        3,
        [[0, 1, 100], [1, 2, 100], [0, 2, 500]],
        0,
        2,
        0,
    ) == 500

    assert s.findCheapestPrice(
        4,
        [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]],
        0,
        3,
        1,
    ) == 500

    assert s.findCheapestPrice(
        4,
        [[0, 1, 100], [1, 2, 100], [2, 3, 100], [0, 3, 500]],
        0,
        3,
        2,
    ) == 300

    assert s.findCheapestPrice(
        3,
        [[0, 1, 100]],
        0,
        2,
        1,
    ) == -1

    print("all tests passed")

run_tests()
```

Test coverage:

| Test | Why |
|---|---|
| One stop allowed | Cheaper route uses one intermediate city |
| Zero stops allowed | Only direct flight is valid |
| Cheaper route exceeds stop limit | Ensures stop constraint is enforced |
| Larger stop limit | Allows the cheaper multi-flight path |
| Unreachable destination | Returns `-1` |