All problems

Cheapest Flights Within K Stops

Medium · shortest path

An airline serves n cities, numbered 0 to n - 1. Its one-way flights are given as a list flights of triples [from, to, price]: you can fly from city from to city to for price.

You want to travel from city src to city dst. You are willing to make at most k stops, where a stop is a city you change planes in, strictly between the first and the last city of the trip. So a trip with k stops has at most k + 1 flights, and k = 0 means a direct flight.

Return the smallest total price of such a trip, or -1 if no trip with at most k stops exists.

Several flights may join the same pair of cities, and you may pass through the same city more than once, although doing so is never useful.

Examples

Example 1

Input: n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 1

Output: 200

Fly 0 to 1 and then 1 to 2, with one stop in city 1. That is cheaper than the direct flight.

Example 2

Input: n = 3, flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]], src = 0, dst = 2, k = 0

Output: 500

With no stops allowed only the direct flight is possible.

Example 3

Input: n = 3, flights = [[0, 1, 5]], src = 0, dst = 2, k = 2

Output: -1

No flight ever reaches city 2.

Constraints