5706. Самый дешёвый маршрут с лимитом пересадок
Hard
0 решили
Ориентированный граф городов 0…n−1. Рейсы
flights[i] = [from, to, price]. Найдите минимальную стоимость пути из src в dst не более чем с k пересадками (то есть ≤ k+1 рейс). Если пути нет — −1.Примеры:
Вход:
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
0 <= k <= n
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python и Java, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!