Find the cheapest path from source to destination with at most K stopovers.
You are given `n` cities numbered from `0` to `n-1`, and a list of `flights` where each flight is `[from, to, price]` indicating a directed edge from city `from` to city `to` with cost `price`. You need to find the cheapest price from `src` to `dst` using **at most `K` stops** (i.e., at most `K+1` legs). If no such route exists, return `-1`.
Implement the function `find_cheapest_price(n, flights, src, dst, K)` that returns the minimum total cost.
Note:
- `1 <= n <= 100`
- `0 <= len(flights) <= n*(n-1)`
- Each flight price is a positive integer.
- `src` and `dst` are distinct.
- There may be multiple flights between the same pair of cities; you may choose any.
- A 'stop' is an intermediate city. For example, a direct flight has 0 stops. A path `src -> A -> dst` has 1 stop.
Constraints
1 <= n <= 100
0 <= len(flights) <= n*(n-1)
0 <= price <= 10^4
0 <= src, dst < n, src != dst
0 <= K <= 10
Time: O(K * (n + len(flights))) or similar. Space: O(n + len(flights)).
Example
>>> find_cheapest_price(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1)
200
>>> find_cheapest_price(3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0)
500
>>> find_cheapest_price(4, [[0,1,100],[1,2,100],[2,3,100],[0,3,1000]], 0, 3, 1)
1000
>>> find_cheapest_price(4, [[0,1,100],[1,2,100],[2,3,100],[0,3,1000]], 0, 3, 2)
300
30 points
~30 min