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

Задача

Маршрут курьера

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

Курьер забрал заказ на перекрёстке 1 и должен довезти его до перекрёстка n. Город — это n перекрёстков и m улиц; каждая улица соединяет два перекрёстка, по ней можно ехать в обе стороны, и известна её длина в метрах. Найдите самый короткий маршрут и выведите его целиком — навигатор курьера должен показать, куда поворачивать.

Один из тестов — настоящий Алматы из OpenStreetMap: перекрёсток 1 у площади Республики, перекрёсток n у Зелёного базара.

Вход

В первой строке числа n и m (2 ≤ n ≤ 50 000, 1 ≤ m ≤ 100 000). В каждой из следующих m строк три числа a, b, w: улица между перекрёстками a и b длиной w метров (1 ≤ a, b ≤ n, 1 ≤ w ≤ 10 000). Между двумя перекрёстками бывает несколько улиц; бывают и улицы-петли, которые возвращаются на тот же перекрёсток.

Выход

Если доехать нельзя, выведите -1. Иначе в первой строке — длину кратчайшего маршрута, во второй — число перекрёстков k на нём (вместе с первым и последним), в третьей — сами перекрёстки по порядку, от 1 до n. Если кратчайших маршрутов несколько, подойдёт любой.

Примеры

Пример 1

Вход
6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9
Выход
11
3
1 3 6

Пример 2

Вход
4 2
1 2 5
3 4 1
Выход
-1

Ограничения

Время · Python
4000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
11 тестов

Разбор

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

1Подсказка 1

Поиск в ширину находит путь с наименьшим числом улиц. Но улица в 10 км и улица в 10 м для него одинаковы. Посмотрите на второй пример: какой маршрут выберет поиск в ширину и какой нужен на самом деле?

2Подсказка 2

Кроме длины нужен и сам путь. Когда вы улучшаете расстояние до перекрёстка, запомните, откуда пришли. Как потом пройти по этим записям от финиша к старту?

3Идея

Это классический алгоритм Дейкстры: длины положительные, нужен кратчайший путь из одной вершины. Для восстановления пути храним массив parent: при каждой удачной релаксации ребра (u, v) записываем parent[v] = u. Последняя запись для v соответствует окончательному расстоянию — ведь после того, как v достали из кучи, его расстояние уже не меняется.

4Разбор

Читаем граф в списки смежности, добавляя каждую улицу в обе стороны. Запускаем Дейкстру из 1 с двоичной кучей и ленивым удалением. Как только из кучи достали n, можно остановиться: его расстояние окончательное.

Если dist[n] осталось бесконечным, выводим −1. Иначе идём от n по parent, пока не дойдём до 1, и переворачиваем список. Рекурсия здесь не нужна и даже вредна: в одном из тестов маршрут проходит через 50 000 перекрёстков, и рекурсивное восстановление упрётся в глубину стека Python.

Петли и повторные улицы ничего не ломают: петля никогда не улучшит расстояние (длина положительна), а из нескольких улиц между одной парой перекрёстков релаксация сама выберет самую короткую.

4+Решение
5Сложность

O((n + m) log n) времени и O(n + m) памяти. При m = 10⁵ это около двух миллионов элементарных шагов — доли секунды даже на Python.

6Типичные ошибки
  • Поиск в ширину вместо Дейкстры. Проходит первый пример, где самые короткие маршруты случайно оказываются и самыми «короткими по числу улиц», и падает на втором тесте, где одна длинная улица ведёт прямо к цели.
  • Пометка «посещено» в момент добавления в кучу. Так делают в поиске в ширину, но у Дейкстры вершина может улучшиться после того, как в первый раз попала в кучу. Помечать надо в момент извлечения.
  • Медленный ввод на Python. Сто тысяч вызовов input() заметно медленнее одного sys.stdin.buffer.read(). См. приём быстрый ввод-вывод.
  • Рекурсивное восстановление пути. Цепочка из 50 000 перекрёстков вызывает RecursionError.

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

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