MediumPro challengePythonJavaScriptTypeScript
Graph — Cheapest Flights Within K Stops
Data StructuresGraphsBellman-FordDynamic Programming
solve(n, flights, src, dst, k) — n cities 0..n-1; each[from, to, price] is a one-way flight. Return the cheapest price from src
to dst using at most `k` stops (so at most k + 1 flights), or -1 if
that is impossible.
The cheapest path overall may need too many stops, so plain Dijkstra on price is
not enough. Run Bellman–Ford for exactly `k + 1` rounds, relaxing from the
previous round's costs only.
Examples (flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]])
solve(4, flights, 0, 3, 1) → 700 // 0→1→3
solve(4, flights, 0, 3, 2) → 400 // 0→1→2→3
solve(4, flights, 0, 3, 0) → -1 // no direct flight
solve(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0) → 500Sample tests
Test #1One stop
Input: [4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1]
Output: 700
Test #2Two stops are cheaper
Input: [4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,2]
Output: 400
Test #3No direct flight
Input: [4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,0]
Output: -1