Пересадки
Сервис поиска билетов отвечает на вопрос «сколько перелётов нужно, чтобы добраться из аэропорта s в аэропорт t». Расписание не важно, важны только направления: перелёт из a в b ещё не значит, что есть перелёт обратно. Запросов много, и на каждый нужно отвечать быстро.
Тесты 3–5 — настоящая сеть рейсов всего мира: 3468 аэропортов и 84 869 направлений из базы позывных Virtual Radar Server. В четвёртом тесте — все маршруты из Алматы и в Алматы.
Вход
В первой строке число аэропортов n и число направлений m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 10⁵). Дальше m строк a b: есть перелёт из a в b (1 ≤ a, b ≤ n, a ≠ b, повторов нет). Затем число запросов q (1 ≤ q ≤ 10⁴) и q строк s t.
Выход
q строк: наименьшее число перелётов из s в t, или -1, если долететь нельзя. Если s = t, ответ 0.
Примеры
Пример 1
6 8 1 2 1 4 2 3 3 5 4 2 4 5 5 3 5 6 4 1 6 1 5 6 1 3 3
3 2 -1 0
Пример 2
5 6 1 2 2 3 3 1 3 4 4 3 2 5 5 1 4 4 1 5 1 1 5 5 5
3 2 -1 2 0
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Один запрос — это обычный поиск в ширину. Посчитайте, сколько аэропортов он отметит на сети всего мира, если из любого места в любое долетают за три-четыре перелёта. А сколько запросов?
2Подсказка 2
Пустите две волны: от s по рейсам и от t по рейсам задом наперёд. Сколько аэропортов отметит каждая, если им достаточно пройти по два перелёта? И когда можно остановиться — посмотрите на первый пример.
3Идея
Двунаправленный поиск в ширину, в котором волны растут целыми слоями, и каждый раз растёт та, у которой текущий слой меньше. Первое же касание — перелёт из нового аэропорта одной волны в аэропорт, уже отмеченный другой, — даёт ответ. В сети, где каждый перелёт умножает охват, две волны глубины d/2 отмечают порядка корня из того, что отмечает одна волна глубины d.
4Разбор
Храним два списка смежности: out[a] — куда можно улететь из a, into[b] — откуда можно прилететь в b. Волна от s ходит по out, волна от t — по into. У каждой волны — словарь «аэропорт → глубина» и текущий слой. Выбираем волну с меньшим слоем, обходим весь её слой; если сосед уже отмечен другой волной, ответ — глубина текущего слоя + 1 + глубина соседа в другой волне.
Почему первое касание уже кратчайшее. Пусть волна от s обошла слои до глубины ks, волна от t — до kt, и касаний ещё не было. Значит, отмеченные множества не пересекаются: нет аэропорта, до которого от s не больше ks перелётов, а от него до t — не больше kt. На кратчайшем маршруте длины L аэропорт после ks перелётов находится в L − ks перелётах от t, поэтому L > ks + kt. А касание при обходе слоя глубины ks даёт маршрут длины ks + 1 + (глубина в другой волне) ≤ ks + 1 + kt. Это и есть минимум.
Словари вместо массивов длины n: запрос трогает сотню-другую аэропортов, а очищать массивы на 10⁴ элементов после каждого из 10⁴ запросов — это 10⁸ лишних записей. В Go вместо словарей — общие массивы с «номером запроса»: аэропорт считается отмеченным, только если в нём записан номер текущего запроса.
4+Решение
5Сложность
В худшем случае — цепочка без разветвлений, как в шестом тесте, — запрос стоит O(n + m), как и одна волна. На сети рейсов запрос отмечает в среднем полторы сотни аэропортов вместо полутора тысяч у одной волны и останавливается, просмотрев лишь часть их рейсов: на Python эталон отвечает на запросы о сети мира в десятки раз быстрее одной волны, и одна волна не укладывается в ограничение времени.
6Типичные ошибки
- Аэропорты по одному, из двух очередей по очереди. Самая частая ошибка: волны чередуются не слоями, а отдельными аэропортами, и поиск останавливается на первом касании. Тогда в очереди волны лежат аэропорты двух соседних слоёв, и касание может прийти через более глубокий. В первом примере ответ 1 → 6 получается 4 вместо 3: волна от 6, разбирая аэропорт 5, первым видит аэропорт 3, до которого волна от 1 добралась только вторым перелётом, и останавливается, не взглянув на аэропорт 4 — а до него от 1 один перелёт. Это
wrong.py; на сети мира он ошибается на единицу примерно в каждом шестом запросе. - Вторая волна по рейсам «туда». Рейс a → b не означает рейса b → a. Во втором примере из аэропорта 5 никуда не улететь, хотя прилететь в него можно.
- Одна волна. Ответы верные, но на сети мира поиск в ширину до финиша отмечает в среднем полторы тысячи аэропортов, и десять тысяч запросов не укладываются во время.