Cheapest Route With Limited Layovers
There are n cities numbered 0 to n - 1. Each entry [from, to, price] of flights is a one-way flight.
Return the cheapest total price to travel from src to dst using at most k layovers (a layover is an intermediate city, so at most k + 1 flights). If no such route exists, return -1. Travelling from a city to itself costs 0.
Example 1
Input: n = 4, flights = [[0,1,50],[1,2,40],[0,2,120],[2,3,30],[1,3,200]], src = 0, dst = 3, k = 1 Output: 150 Explanation: 0 → 2 → 3 costs 150; the cheaper 0 → 1 → 2 → 3 needs two layovers.
Example 2
Input: n = 4, flights = [[0,1,50],[1,2,40],[0,2,120],[2,3,30],[1,3,200]], src = 0, dst = 3, k = 2 Output: 120 Explanation: With two layovers allowed, 0 → 1 → 2 → 3 costs 120.
Constraints
- 1 <= n <= 300
- 0 <= flights.length <= 5000
- 1 <= price <= 1000
- 0 <= src, dst, k < n
Hint 1
Run Bellman-Ford for exactly k + 1 rounds.
Hint 2
In each round, relax edges using the distances from the previous round only, so a round adds at most one flight.
Good practice for: Backend Developer, Full Stack Developer, Data Engineer, Cloud Engineer, Mobile App Developer
Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.