PreviousNext
Coding/Dynamic programming

Cheapest flights k stops

Write codeMedium30 min

Your task

There are n cities (0..n-1) connected by directed flights, where flights[i] = [from, to, price]. Given a source src, a destination dst, and an integer k, return the cheapest price to fly from src to dst using at most k intermediate stops (i.e. at most k+1 flights). If there is no such route, return -1.

Examples

cheapest_flights_k_stops(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int
Example 1
Inputcheapest_flights_k_stops(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1)
Output700