Запасной маршрут
Пожарной части нужно два маршрута от депо до объекта: основной и запасной. Чтобы перекрытый перекрёсток не задел оба сразу, у маршрутов не должно быть общих перекрёстков, кроме начала и конца. Из всех таких пар нужна та, у которой сумма длин наименьшая. Если пары нет, так и скажите.
Тесты 3–4 — настоящие улицы центра Алматы из OpenStreetMap: 7909 перекрёстков; в третьем тесте маршруты ведут от пожарных частей к известным местам города. Все улицы считаются двусторонними.
Вход
В первой строке n и m — число перекрёстков и улиц (2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 2 · 10⁴). Дальше m строк a b ℓ: улица длиной ℓ метров между перекрёстками a и b (a ≠ b, 1 ≤ ℓ ≤ 10⁴, между двумя перекрёстками не больше одной улицы). Затем число запросов q (1 ≤ q ≤ 20) и q строк s t (s ≠ t).
Выход
Для каждого запроса — наименьшая сумма длин двух маршрутов из s в t без общих перекрёстков, кроме s и t, или -1, если такой пары нет. Улица прямо из s в t — тоже маршрут, но только один.
Примеры
Пример 1
4 4 1 2 3 2 4 4 1 3 5 3 4 6 3 1 4 1 2 2 3
18 18 18
Пример 2
7 8 1 2 1 2 3 1 3 4 1 1 5 2 5 3 2 2 6 2 6 4 2 4 7 1 3 1 4 1 5 1 7
10 6 -1
Ограничения
- Время · Python
- 12500 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Самый короткий маршрут, а потом самый короткий в обход его перекрёстков? Посмотрите на второй пример: кратчайший маршрут 1 → 2 → 3 → 4 занимает оба перекрёстка, через которые можно обойти, и второго маршрута в обход нет. А пара есть: 1 → 5 → 3 → 4 и 1 → 2 → 6 → 4.
2Подсказка 2
Два маршрута без общих перекрёстков — это поток величины 2, в котором через каждый перекрёсток проходит не больше единицы. Что делать с перекрёстком, чтобы ограничить поток через него? И что минимизировать?
3Идея
Каждый перекрёсток v превращаем в две вершины, въезд и выезд, с дугой ёмкости 1 между ними; у s и t ёмкость 2. Каждая улица — две дуги ёмкости 1 и стоимости ℓ, по одной в каждую сторону. Ответ — поток наименьшей стоимости величины 2 из s в t: две единицы, каждая по самому дешёвому пути в остаточной сети. Второй путь может пройти часть первого задом наперёд — по обратным дугам с отрицательной стоимостью — и тем самым отнять у первого маршрута его кусок. Во втором примере так и выходит: 1 → 5 → 3, назад 3 → 2, затем 2 → 6 → 4.
4Разбор
Сеть строим один раз, а для каждого запроса копируем массив ёмкостей и ставим 2 на дугах s и t. Два поиска Дейкстрой по приведённым стоимостям c + π(u) − π(v): перед первым все потенциалы нули, после каждого к ним прибавляются расстояния. Если второй поиск не дошёл до стока, пары нет — ответ −1. Стоимость потока — сумма стоимостей пройденных дуг, отрицательные отмены уже вычтены.
Почему две независимые дуги на улицу, а не одна неориентированная: второй путь может пройти по улице первого навстречу ему, и это должна быть обратная дуга с отрицательной стоимостью, а не ещё одна единица потока по той же улице.
4+Решение
5Сложность
Два поиска по сети из 2n вершин и 2n + 4m дуг: O((n + m) log n) на запрос. Так же устроен алгоритм Суурбалле: ровно два поиска кратчайшего пути.
6Типичные ошибки
- Кратчайший, потом кратчайший в обход. Это
wrong.py. Во втором примере он не находит второго маршрута. На улицах Алматы, среди запросов, где пара есть, он ошибается в 10 из 17 в третьем тесте и в 16 из 19 в четвёртом: пара выходит длиннее, а однажды второго маршрута нет вовсе. В седьмом тесте кратчайший маршрут виляет между двумя рельсами длинной лестницы и закрывает обе, хотя сами рельсы — наилучшая пара. - Без разрезания перекрёстков. Ёмкость 1 только на улицах даёт маршруты без общих улиц, но с общими перекрёстками.
- Дейкстра без потенциалов на втором поиске: обратные дуги первого пути отрицательные, и обычная Дейкстра может вернуть не самый дешёвый путь.
Алгоритмы задачи
O(F · E log V)
2 задачи
GRA
Алгоритм
Алгоритм Дейкстры
Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер.
O((V + E) log V)
3 задачи