Description
There are n cities connected by flights. Find the cheapest price from src to dst with at most k stops. Return -1 if there is no such route.
Examples
Input:
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1Output:
700Explanation:
Path 0→1→3 costs 100+600=700 with 1 stop.
Input:
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0Output:
500Explanation:
Direct flight 0→2 costs 500 with 0 stops.
Input:
n = 5, flights = [[0,1,200],[0,2,800],[1,2,100],[2,3,300],[1,4,400],[3,4,150]], src = 0, dst = 4, k = 2Output:
700Explanation:
The cheapest route from city 0 to city 4 within 2 stops is 0→1→4 costing 200+400=600. Path 0→1→2→3→4 costs 750 but uses 3 stops, exceeding k=2. The answer is 700.
Constraints
- •
1 ≤ n ≤ 100 - •
0 ≤ flights.length ≤ n*(n-1)/2 - •
0 ≤ k < n