Cheapest Flights Within K Stops Problem

Cheapest Flights Within K Stops Problem — ExecCode Medium DSA Practice

Solve the Cheapest Flights Within K Stops problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

There are n cities connected by flights [from, to, price]. Find the cheapest price from src to dst with at most k stops. Return -1 if impossible.

Examples

Input n = 5, flights = [[0, 1, 100], [1, 2, 100], [2, 4, 100], [0, 3, 300], [3, 4, 100], [0, 4, 700]], src = 0, dst = 4, k = 2; Output 300. Input n = 5, flights = [[0, 1, 100], [1, 2, 100], [2, 4, 100], [0, 3, 300], [3, 4, 100], [0, 4, 700]], src = 0, dst = 4, k = 1; Output 400

Constraints

1 ≤ n ≤ 100 0 ≤ flights.length ≤ n*(n-1)/2 0 ≤ k < n Prices ≥ 0

Practice Cheapest Flights Within K Stops free on ExecCode. Browse DSA problems, topic map, and placement guides.