A travel site searches n cities numbered 0 to n - 1. Each flights[i] = [from, to, price] is a one-way flight. Travelers set a limit k on layovers: a trip may stop in at most k cities between src and dst, so it uses at most k + 1 flights.
Write cheapestTrip(n, flights, src, dst, k) that returns the lowest total price from src to dst within the layover limit, or -1 if there is no such trip. src and dst are different.
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,3,500],[1,3,600]], src = 0, dst = 3, k = 1 Output: 500
With at most 1 layover, the options are the direct flight (500) and 0 → 1 → 3 (700).
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,3,500],[1,3,600]], src = 0, dst = 3, k = 2 Output: 300
Two layovers allow 0 → 1 → 2 → 3 for 300.
2 <= n <= 1000 <= flights.length <= 50001 <= price <= 10^40 <= k < nRun tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #463 Cheapest Itinerary With Limited Layovers. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.