Cheapest Flight Planner with K Stop Limit

You are given a directed flight network and must return the cheapest route from source to destination using at most k stops. The graph may be sparse or dense, and the algorithm must avoid exponential path exploration. Pattern focus: Bellman-Ford. Keep only the best distance for each node at each stop count.

Input Format

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

Output Format

minimum price with at most k stops, or -1

Constraints

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

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 under the stop limit.

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:

Two intermediate cities are allowed and produce a cheaper route.

Example 3:

Input:

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

Output:

-1

Explanation:

No route reaches the destination.

Loading...
Cheapest Flight Planner with K Stop Limit