Cheapest Flights Within K Stops

Problem

Find the cheapest price from src to dst using at most k stops, where a stop is an intermediate city.

flights is a list of [u, v, w] directed edges between n cities. Use Bellman-Ford style relaxation limited to k + 1 rounds, reading from a frozen copy of the previous distances so each round adds at most one flight. Return -1 when there is no route within the stop limit.

Hint

Copy the distance array before each round so one round means one more flight.

Test cases

case 1

in: [3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1]

expected: 200

case 2

in: [3,[[0,1,100],[1,2,100],[0,2,500]],0,2,0]

expected: 500

case 3

in: [3,[[0,1,100],[1,2,100]],0,2,5]

expected: 200

case 4

in: [2,[[0,1,50]],1,0,3]

expected: -1

case 5

in: [1,[],0,0,0]

expected: 0

Starter codePython

def find_cheapest_price(n, flights, src, dst, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor