There are n cities 0 .. n - 1. Each (frm, to, price) in flights is a one-way flight (price >= 1, no self-loops, at most one flight per ordered pair).
Write find_cheapest_price(n, flights, src, dst, k) -> int returning the cheapest total price from src to dst using at most k intermediate stops (so at most k + 1 flights), or -1 if no such route exists.
flights = [(0, 1, 100), (1, 2, 100), (0, 2, 500)]
find_cheapest_price(3, flights, 0, 2, 1) # 200 (0 -> 1 -> 2)
find_cheapest_price(3, flights, 0, 2, 0) # 500 (direct only)
If src == dst the answer is 0.
Constraints: 1 <= n <= 100, 0 <= k < n, 0 <= src, dst < n, 1 <= price <= 10**4. Enumerating every route is exponential; the tests include 60 cities with nearly every flight present and k = 40, so aim for something like O(k · E).
Watch out: the cheapest way to reach a middle city may use too many stops, while a pricier way with fewer stops is the one that leads to the answer.
Show hint
build the answer up by number of flights used: from the best prices using at most i flights, one pass over all flights gives the best prices using at most i + 1. Make sure one pass can't chain two flights together.