Cheapest Flights Within K Stops

Given a list of directed flights with prices, return the cheapest price from source to destination using at most k stops. Pattern focus: Relaxation. Distance updates must respect the stop limit, so the state is not just the node but also how many edges have been used.

Input Format

n = city count, flights = directed weighted edges, src = source city, dst = destination city, k = maximum stops

Output Format

minimum price with at most k stops, or -1

Constraints

  • 1 <= n <= 100
  • 1 <= flights.length <= 10^4
  • 0 <= price <= 10^4
  • 0 <= k <= 99

Examples

Example 1:

Input:

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

Output:

500

Explanation:

The direct flight is the cheapest option within one stop.

Example 2:

Input:

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

Output:

300

Explanation:

The path with two intermediate cities is cheaper and still valid.

Example 3:

Input:

n = 3
flights = [[0,1,50]]
src = 0
dst = 2
k = 1

Output:

-1

Explanation:

The destination is unreachable.

Loading...
Cheapest Flights Within K Stops - Shortest Path