Войти Регистрация
Алгоритмы

95. Маршрут не больше чем с k пересадками

Сложная

В городе n остановок, номера от 0 до n − 1. Рейс [u, v, t] везёт от остановки u до v за t минут; обратно — только если есть отдельный рейс.

Пассажир едет из src в dst и готов сделать не больше k пересадок, то есть проехать не больше k + 1 рейсов. Верните минимальное время в пути или -1, если так не доехать. Ожидание на остановках не считаем.

В работе: Маршруты в Картах: многие не пересаживаются больше двух раз, даже если так на 5 минут быстрее.

Пример 1

Ввод
n = 4
rides = [[0, 1, 30], [0, 2, 10], [2, 1, 10], [1, 3, 10]]
src = 0
dst = 3
k = 1
Вывод
40

Через остановку 2 быстрее (30 минут), но это 3 рейса и 2 пересадки. С одной пересадкой — 0 → 1 → 3 за 40.

Пример 2

Ввод
n = 4
rides = [[0, 1, 30], [0, 2, 10], [2, 1, 10], [1, 3, 10]]
src = 0
dst = 3
k = 2
Вывод
30

Две пересадки разрешены — 30 минут.

Ограничения

  • 1 ≤ n ≤ 10⁴
  • 0 ≤ число рейсов ≤ 5·10⁴
  • 1 ≤ t ≤ 1000
  • 0 ≤ k ≤ 20
  • Лимит — 3 с на тест (3000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def route_limited_transfers(n, rides, src, dst, k):
ГрафыДейкстраСостояние в вершинецельO(n log n)

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.