Запросы по ярусам
Предподсчёт навигатора уже сделан: перекрёстки упорядочены по важности, и к улицам добавлены ярлыки — рёбра, которые заменяют пути через неважные перекрёстки. Каждое ребро получившегося графа записано снизу вверх: от менее важного конца к более важному. Ехать по ребру, разумеется, можно в обе стороны.
Граф построен сжатием, и поэтому у него есть главное свойство иерархии: для любых двух перекрёстков s и t среди кратчайших путей между ними есть такой, который сначала только поднимается к более важным перекрёсткам, а потом только спускается. Ответьте на запросы о кратчайших расстояниях — быстрее, чем обычной Дейкстрой по всему графу.
Тесты 3 и 4 — иерархия улиц центра Алматы, построенная предподсчётом из статьи: 7909 перекрёстков, 10 389 улиц и 12 545 ярлыков.
Вход
В первой строке число перекрёстков n и число рёбер иерархии m (1 ≤ n ≤ 10⁴, 0 ≤ m ≤ 3·10⁴). Дальше m строк a b w: ребро длины w между a и b, где a менее важен, чем b (1 ≤ w ≤ 10⁷). Затем число запросов q (1 ≤ q ≤ 5000) и q строк s t.
Выход
q строк: длина кратчайшего пути из s в t или -1, если пути нет.
Примеры
Пример 1
5 5 1 3 5 1 4 2 2 4 1 5 4 9 3 4 7 4 3 1 2 5 5 3 1 1
5 10 16 0
Пример 2
6 5 1 2 4 1 3 7 4 5 1 6 5 1 2 3 4 4 1 3 3 4 6 4 5 5
7 -1 2 0
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Обычная Дейкстра по всему графу (рёбра в обе стороны) даёт верные ответы, но на городе в восемь тысяч перекрёстков она осматривает в среднем четыре тысячи на запрос. Как воспользоваться тем, что кратчайший путь можно искать в виде «вверх, потом вниз»?
2Подсказка 2
Подъём от s — это Дейкстра от s только по рёбрам снизу вверх. Спуск к t, прочитанный задом наперёд, — тоже подъём, только от t. Две волны, и обе ходят по одним и тем же рёбрам «вверх».
3Подсказка 3
Когда остановить волны? Правило из двунаправленного поиска — «сумма двух наименьших ключей не меньше лучшего пути» — проверьте на первом примере.
4Идея
Запустим две Дейкстры по рёбрам вверх: от s и от t, по очереди, каждый раз ту, у которой наименьший ключ меньше. Когда волна достаёт вершину, у которой есть метка другой волны, это вершина «на вершине» какого-то пути вверх-вниз, и лучший путь best обновляется. Волна заканчивается, когда её наименьший ключ не меньше best: любой путь вверх-вниз короче best поднимается из её конца не выше, чем на best, а значит, его верхнюю вершину эта волна уже достала.
5Разбор
Рёбра храним только «вверх»: up[a] — пары (b, w). Для каждого запроса — две кучи, два словаря расстояний и два множества обработанных вершин. Выбираем сторону с меньшей вершиной кучи; устаревшие записи пропускаем; если ключ не меньше best, очищаем эту кучу. Иначе вершина обработана: если у неё есть метка другой стороны, пробуем улучшить best; дальше обычная релаксация по up.
Почему ответ верный. Пусть P — кратчайший путь вида «вверх, потом вниз» с верхней вершиной x; его подъём от s до x имеет длину a, подъём от t до x — b, и a + b = δ(s, t). Пока best > δ, ключи волны от s, меньшие a < best, ещё будут доставаться, и Дейкстра по рёбрам вверх достанет x с расстоянием не больше a; то же для волны от t. Когда x достанет вторая из волн, best станет не больше a + b. А больше δ он быть не может: это длина настоящего пути. Подробнее — в статье об иерархиях сжатия.
5+Решение
6Сложность
Каждый запрос — две маленькие Дейкстры по верхушке иерархии: на улицах Алматы они осматривают в среднем около 120 перекрёстков вместо 4000 у обычной Дейкстры. В худшем случае — O((n + m) log n) на запрос, как и у Дейкстры, но на графах, где иерархия удалась, это редкость.
7Типичные ошибки
- Остановка двунаправленной Дейкстры. Правило «сумма наименьших ключей ≥ best» опирается на то, что каждая волна — честная Дейкстра по одному и тому же графу и её ключи — настоящие расстояния от конца. Волна вверх видит не весь граф, и её ключи — длины путей вверх, а не кратчайших путей. В первом примере волна от 3 сразу поднимается к вершине 4 (ключ 7), волна от 1 — к 4 (ключ 2), и сумма 9 обновляет best = 9. Ключи 7 и 5 в сумме уже больше 9, и правило останавливает поиск, хотя волна от 1 ещё не достала вершину 3, через которую путь всего 5. Это
wrong.py; на улицах Алматы он ошибается примерно на половине запросов. - Остановка при первой встрече. Первая вершина, которую достали обе волны, обычно не вершина кратчайшего пути: ошибок ещё больше.
- Дейкстра по всему графу. Ответы верные, но на тысячах запросов к городу это в десятки раз медленнее, и Python не укладывается во время.
Алгоритмы задачи
O((V + E′) log V)
1 задача
GRA
Алгоритм
Двунаправленный поиск
Две волны Дейкстры навстречу друг другу: где остановиться, сколько экономится и как подружить с A*.
O((V + E) log V)
2 задачи