Shipping Route: Find the Cheapest Shipping Route with At Most K Stops

Question

## Problem

You are given `n` cities and a list of flights `(source, destination, price)`. Find the cheapest route from `src` to `dst` with at most `k` intermediate stops. Return the cost, or -1 if no such route exists.

```python
from typing import List

def cheapest_route(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
    # flights: [[from, to, price], ...]
    # k: maximum number of stops (not counting src and dst)
    # return: minimum cost, or -1
    pass
```

**Example:**
```
n=4, flights=[[0,1,100],[1,2,100],[2,3,100],[0,2,500]]
src=0, dst=3, k=1

0->1->2->3: 3 stops but k=1 only allows 1 intermediate -> too many stops
0->2->3: 1 stop, cost=500+100=600

Output: 600
```

## Approach

Bellman-Ford with k+1 relaxation rounds. At round `i`, `dp[v]` = min cost to reach `v` with at most `i` edges. Time: O(k * |flights|).

## Follow-ups

1. Why does standard Dijkstra not directly apply here (without modification)?
2. How would you modify BFS/Dijkstra with a (cost, stops) state to solve this?
3. What changes if you need to maximize the number of stops within budget (opposite optimization)?
4. How would you handle the case where flights have different durations in addition to prices?

Shipping Route: Find the Cheapest Shipping Route with At Most K Stops

Question Details

Full Details

Topics

More from Stripe