You are given n cities connected by some number of flights. You are given an array flights where flights[i] = [from, to, price] represents a flight from city from to city to with cost price.
You are also given three integers src, dst, and k. Return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
A stop is any intermediate city between src and dst — the source and destination themselves do not count as stops.
Example 1:
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation: The cheapest path with at most 1 stop is 0 → 1 → 3 with cost 100 + 600 = 700. The path 0 → 1 → 2 → 3 costs 400 but uses 2 stops, which exceeds k = 1.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation: The cheapest path with at most 1 stop is 0 → 1 → 2 with cost 100 + 100 = 200, which is cheaper than the direct flight 0 → 2 costing 500.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: With k = 0 stops, only direct flights are allowed. The direct flight 0 → 2 costs 500.
1 <= n <= 1000 <= flights.length <= n * (n - 1) / 2flights[i].length == 30 <= from, to < nfrom != to1 <= price <= 100000 <= src, dst, k < nsrc != dst