Cheapest Trip With Few Layovers

Medium

There are cities cities numbered 0 to cities - 1 and a list of direct flights flights: flight [a, b, price] goes from city a to city b and costs price. You need to get from city origin to city destination with at most max_stops layovers (intermediate cities). Return the lowest total cost of such a trip, or -1 if it is impossible.

Example 1

cities=4, flights=[[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 300]], origin=0, destination=3, max_stops=1 → 100

The route 0 → 2 → 1 → 3 costs 80 but has two layovers. With at most one, the best is 0 → 1 → 3 for 100.

Example 2

cities=4, flights=[[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 300]], origin=0, destination=3, max_stops=2 → 80

Two layovers are now allowed, so 0 → 2 → 1 → 3 for 80 works.

Example 3

cities=3, flights=[[1, 0, 40]], origin=0, destination=2, max_stops=2 → -1

There are no flights out of city 0 at all.

Constraints

1 ≤ cities ≤ 100
0 ≤ len(flights) ≤ cities·(cities − 1) / 2
flights[i] = [a, b, price], 0 ≤ a, b < cities, a ≠ b
1 ≤ price ≤ 10⁴
At most one flight per ordered pair of cities
0 ≤ origin, destination, max_stops < cities, origin ≠ destination

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph Dynamic Programming Shortest Path Heap (Priority Queue)

Similar problems

Shortest Path of a Rolling Ball Medium Broadcast Reach Time Medium Ball Into the Hole Hard Roads on the Fastest Routes Hard Ratio Chain Queries Medium

Input

cities=4, flights=[[0, 1, 50], [1, 3, 50], [0, 2, 20], [2, 1, 10], [0, 3, 300]], origin=0, destination=3, max_stops=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 92 tests on the server, hidden ones included.