5706. Самый дешёвый маршрут с лимитом пересадок
Hard
0 решили
Ориентированный граф городов
k = 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 <= n <= 100<br>0 <= k <= n<br>0 <= flights.length <= n·(n−1)<br>1 <= price <= 10^4<br>Стоимость влезает в 32-битный int.
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!