Implement the cheapestFlightWithinKStops method that finds the cheapest price from source to destination within a stop limit.

You are given flight routes as [from, to, price], the number of cities, a source city, a destination city, and the maximum number of allowed stops.

Return the cheapest price from source to destination using at most that many intermediate stops. If the destination cannot be reached within the limit, return -1.

Example 1

Input
nodes (int) = 4
flights (int[][]) = [[0,1,100],[1,2,100],[2,3,100],[0,3,500]]
size (int) = 4
source (int) = 0
destination (int) = 3
stops (int) = 1
Returns (int) 500

Example 2

Input
nodes (int) = 4
flights (int[][]) = [[0,1,100],[1,2,100],[2,3,100],[0,3,500]]
size (int) = 4
source (int) = 0
destination (int) = 3
stops (int) = 2
Returns (int) 300

Example 3

Input
nodes (int) = 3
flights (int[][]) = [[0,1,100],[1,2,100],[0,2,500]]
size (int) = 3
source (int) = 0
destination (int) = 2
stops (int) = 1
Returns (int) 200

Use a bounded Bellman-Ford style dynamic programming approach.

With at most k stops, the path may use at most k + 1 flights. Repeatedly relax all flights, but each round must use a copy of the previous distances so that one round adds only one more flight.

After k + 1 rounds, the destination distance is the cheapest valid price.

Pseudocode:

function cheapestFlightWithinKStops(nodes, flights, size, source, destination, stops):
    distance = array filled with infinity
    distance[source] = 0
    repeat stops + 1 times:
        nextDistance = copy of distance
        for each flight [from, to, price]:
            if distance[from] is not infinity:
                nextDistance[to] = min(nextDistance[to], distance[from] + price)
        distance = nextDistance
    if distance[destination] is infinity:
        return -1
    return distance[destination]
Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run

Notifications

Updates are enabled for this browser.

Receive new tutorials, articles and learning resources. You can turn updates off anytime.

Test browser code

Use this code in admin to send a test notification to this browser.