Practice - Cheapest Flights

Try this practice problem: you have $n$ cities and $m$ flights. Each flight goes from city $u$ to city $v$ with price $w$. Find the cheapest flight from city src to city dst with at most $k$ stops. This is shortest path with a constraint. You cannot use standard DAG DP because you need to track the number of stops.

Use DP with state dp[u][stops] = cheapest cost to reach city $u$ with exactly $stops$ stops. Process in BFS order (by number of stops), and relax edges for each stop count.