1643. Cheapest Within a Stop Limit
Flights are directed edges with a price. Print the cheapest total price from
s to t using at most k intermediate stops, or -1 if there is no such
route. At most k stops means at most k + 1 flights.
This is where a shortest-path habit costs you the interview. Dijkstra finalises a vertex at its cheapest price and never revisits it, and here that is exactly wrong: the cheapest way to reach a city might use too many flights, while a DEARER route that uses fewer is the one that can still be extended. A single best price per city is not enough information.
Bellman-Ford suits it precisely, because its rounds already count edges. After
round r, every price uses at most r flights, so running k + 1 rounds
answers the question directly.
One detail decides correctness: each round must read the PREVIOUS round's prices, not the ones it is writing. Updating in place lets two flights be taken inside a single round, which quietly allows more flights than the limit.
Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ 10000` - `1 ≤ s, t ≤ n` - `0 ≤ k ≤ n` - `0 ≤ w ≤ 10000`
Input
The first line contains five integers n, m, s, t and k.
Each of the next m lines contains three integers u, v and w: a flight from u to v costing w.
Output
Print the cheapest total price from s to t using at most k intermediate stops, or -1 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.