Задачник Базовый курс EN

Заехать по пути

кратчайший путь взвешенный граф куча карты и навигация двоичный поиск

Курьер везёт заказ от точки A до точки B через центр Алматы. По пути ему нужно заехать ещё в одно место — за кофе, в аптеку, к банкомату, — и он готов проехать не больше чем на D метров длиннее кратчайшего маршрута. Через сколько перекрёстков можно проложить такой маршрут? Перекрёсток v подходит, если кратчайший путь из A в v и дальше из v в B длиннее кратчайшего пути из A в B не больше чем на D.

Улицы бывают с односторонним движением. Курьер честный и едет только по правилам — в том числе на пути от v к B. Подбирать нужно сразу для многих значений D: курьер ещё не решил, насколько готов задержаться.

Тесты 3–5 — настоящие улицы центра Алматы с односторонним движением, как оно отмечено в OpenStreetMap. Остальные придуманы.

Вход

В первой строке число перекрёстков n и число участков улиц m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 2·10⁵). Дальше m строк a b w: по участку можно проехать от перекрёстка a к перекрёстку b, его длина w метров (1 ≤ a, b ≤ n, 1 ≤ w ≤ 10⁴). Улица с движением в обе стороны записана двумя строками. Затем строка с номерами A и B (A и B могут совпадать; из A в B проехать можно). Затем число q (1 ≤ q ≤ 10⁵) и строка из q чисел D (0 ≤ D ≤ 10⁹).

Выход

Одну строку из q чисел через пробел: для каждого D в порядке ввода — сколько перекрёстков подходят. Сами A и B, как и все перекрёстки кратчайшего маршрута, подходят при любом D. Перекрёсток, из которого до B не доехать, не подходит никогда.

Примеры

Пример 1

Вход

6 10
1 2 100
2 1 100
2 3 100
3 2 100
3 6 100
1 4 150
4 5 100
5 4 100
5 6 120
6 5 40
1 6
4
0 50 70 100

Выход

4 4 6 6

Пример 2

Вход

Выход

4 4 4

Ограничения

Время · Python: 5000 мс
Время · Go: 1500 мс
Память: 256 МБ
Проверка: 9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Для каждого перекрёстка v нужно знать два числа: сколько ехать от A до v и сколько от v до B. Первое для всех v сразу даёт одна Дейкстра. Как одним запуском получить второе для всех v?

2Подсказка 2

Путь от v до B — это путь от B до v, если ехать по всем улицам задом наперёд. По каким улицам тогда должна идти волна от B?

3Подсказка 3

Когда для каждого перекрёстка известна величина крюка, на каждый запрос нужно ответить, сколько крюков не больше D. Перебирать все перекрёстки на каждый из 10⁵ запросов долго.

4Идея

Это две полные волны двунаправленного поиска: волна от A по улицам в их направлении даёт d(A, v), волна от B по улицам против их направления даёт d(v, B). Крюк через v равен d(A, v) + d(v, B) − d(A, B). Он не отрицателен: путь через v — тоже путь из A в B. Отсортируем крюки и на каждый запрос двоичным поиском найдём, сколько из них не больше D.

5Разбор

Читаем участки и строим два списка смежности: forward[a] с дугами a → b и backward[b] с теми же дугами, развёрнутыми b → a. Дейкстра по forward от A и по backward от B. Перекрёсток, до которого не доехать из A или из которого не доехать до B, пропускаем. Остальные крюки сортируем, и ответ на запрос — bisect_right(extra, D): число крюков, не превосходящих D.

Множество подходящих перекрёстков — это «эллипс» в метрике дорог: точки, сумма расстояний от которых до A и до B не больше d(A, B) + D. На плоскости это был бы настоящий эллипс с фокусами A и B; с односторонними улицами он теряет симметрию, потому что путь до B и путь обратно — разные пути.

5+Решение

6Сложность

Две Дейкстры — O((n + m) log n), сортировка — O(n log n), каждый запрос — O(log n). Наивный ответ на запрос перебором всех перекрёстков стоит O(nq) = 10¹⁰ операций в худшем случае.

7Типичные ошибки

Вторая волна по улицам в их направлении. Так получается расстояние от B до v, а не от v до B. На карте с двусторонними улицами это одно и то же, и ошибка незаметна, а одностороннее движение её выдаёт уже на первом примере: участок 3 → 6 ведёт в B только в одну сторону, и волна от B по улицам «туда» до перекрёстков 1, 2 и 3 не доберётся вовсе. Это wrong.py.
Перекрёстки, где одно из расстояний бесконечно. В Python бесконечность во float прибавится к числу и честно не пройдёт проверку, но если хранить −1 как «недостижимо» и забыть его проверить, крюк выйдет отрицательным и попадёт в ответ при D = 0. Во втором примере тупик 4: заехать в него можно, выехать нельзя.
32-битные числа. Расстояние может доходить до (n − 1) · 10⁴ ≈ 10⁹, а сумма двух расстояний — до 2·10⁹: в языках с 32-битным int это вплотную к пределу 2³¹ − 1 = 2 147 483 647, и любое лишнее слагаемое его перейдёт. В Python и в Go, где int 64-битный, об этом думать не нужно.

Алгоритмы задачи

GRA Алгоритм Двунаправленный поиск Две волны Дейкстры навстречу друг другу: где остановиться, сколько экономится и как подружить с A*. O((V + E) log V) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи