Ctrl K

Меньше всего пересадок на шаттлах

Сложная
По кампусу ездят шаттлы. Шаттл i бесконечно катается по кольцу остановок loops[i]: проходит их по порядку, после последней возвращается к первой и так далее. Вы стоите на остановке start и пока ни в какой шаттл не сели. Нужно попасть на остановку finish, передвигаться можно только на шаттлах; пересаживаться можно на любой остановке, где проходят оба шаттла. Верните наименьшее число шаттлов, в которые придётся сесть по пути. Если доехать невозможно, верните -1.
Пример 1
loops=[[4, 9, 2], [9, 11], [11, 30, 7]], start=4, finish=7 → 3

Садимся на шаттл 0 и едем до 9, пересаживаемся на шаттл 1 до 11, оттуда шаттл 2 довозит до 7: три посадки.

Пример 2
loops=[[1, 3], [5, 8]], start=3, finish=8 → -1

У маршрутов нет общих остановок, так что с остановки 3 до 8 не добраться.

Пример 3
loops=[[6, 2]], start=5, finish=5 → 0

Мы уже на нужной остановке, садиться никуда не нужно.

Ограничения
  • 1 ≤ len(loops) ≤ 5000
  • 1 ≤ len(loops[i]) ≤ 10⁵, остановки внутри одного кольца не повторяются
  • Суммарная длина всех колец не больше 10⁵
  • 0 ≤ loops[i][j] < 10⁶
  • 0 ≤ start, finish < 10⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСемейства слов на один обмен СложнаяКого вылечить первым СложнаяКого отключить от сети СложнаяПобег с огромного поля СложнаяПогасить все лампы Сложная
загружаем Python…
Вход
loops=[[4, 9, 2], [9, 11], [11, 30, 7]], start=4, finish=7
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 80 тестов на сервере, включая скрытые.