5706. Самый дешёвый маршрут с лимитом пересадок

Hard 0 решили
Ориентированный граф городов 0…n−1. Рейсы flights[i] = [from, to, price]. Найдите минимальную стоимость пути из src в dst не более чем с k пересадками (то есть ≤ k+1 рейс).
k = 0 — только прямой рейс. Если src == dst — 0 рейсов, ответ 0. Нет допустимого маршрута → −1. Обычный Дейкстра без учёта k может взять дешёвый путь с лишними пересадками.

Примеры:

Вход: n = 4, flights = [[0,1,100],[1,2,100],[2,3,100],[0,2,500]], src = 0, dst = 3, k = 0
Выход: -1
Объяснение: Без пересадок прямого рейса 0→3 нет.
Вход: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Выход: 200
Объяснение: 0-1-2 дешевле прямого 500.
Вход: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Выход: 500
Объяснение: Без пересадок только прямой рейс.

Ограничения:

1 &lt;= n &lt;= 100<br>0 &lt;= k &lt;= n<br>0 &lt;= flights.length &lt;= n·(n−1)<br>1 &lt;= price &lt;= 10^4<br>Стоимость влезает в 32-битный int.

Теги:

Графы

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!