Skip to content
Onsite
19 / 25

Cheapest Flights Within K Stops

MediumP3Coding

There are n cities labelled 0..n - 1 and a list of directed flights, each [from, to, price]. Find the cheapest total price to travel from src to dst using at most k stops (cities strictly between the start and the end). 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
Why
0 -> 1 -> 3 uses one stop and costs 700.

Example 2

Input
n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output
500
Why
With no stops only the direct flight is allowed.

Constraints

  • 1 <= n <= 100
  • 0 <= flights.length <= n * (n - 1) / 2
  • 0 <= from, to, src, dst < n, src != dst
  • 1 <= price <= 10^4
  • 0 <= k < n

Hints

Run checks the 3 visible tests, Submit all 9.