Дешёвый перелёт не более чем с K пересадками

Графы Сложная

Есть n городов (0..n-1) и список рейсов flights, каждый - тройка [из, в, цена]. Найдите минимальную стоимость перелёта из src в dst, используя не более k пересадок (то есть не более k+1 рейсов). Если долететь за это число пересадок нельзя, верните -1.

Сигнатура функции

cheapest_flight(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int

Примеры

Вход	Ожидаемый результат
[4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1]	700
[3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1]	200

1решили

1пытались

100%успешность

Войдите, чтобы решить →