Loading problem…
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i. 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.
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 route 0 → 1 → 3 costs 100 + 600 = 700 and uses 1 stop. The cheaper route 0 → 1 → 2 → 3 costs 400 but needs 2 stops, which is more than 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 route 0 → 1 → 2 costs 100 + 100 = 200 with one stop, which is cheaper than the direct flight at 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 no stops are allowed, so the only option is the direct flight 0 → 2 costing 500.
Each Bellman-Ford round relaxes edges using distances from the previous round only. Running exactly k+1 rounds allows paths with at most k intermediate stops.
Run checks all cases above. Submit evaluates all test cases.