Minimum Cost to Reach a Destination with K Stops

Given a flight network, return the cheapest cost from source to destination while using at most k stops. Pattern focus: Weighted shortest path. This combines path cost tracking with an explicit stop constraint.

Input Format

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

Output Format

minimum cost 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 valid and cheapest.

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 cheaper multi-stop route is allowed.

Example 3:

Input:

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

Output:

-1

Explanation:

The destination cannot be reached.

Loading...
Minimum Cost to Reach a Destination with K Stops