Тренировочная сессия 18: кратчайшие пути алгоритмом Дейкстры СЕССИЯ

Что тренируем сегодня

«Плато» позади: девять сессий про то, как выбрать состояние и как доказать, что жадный шаг не портит оптимум. «Пик» — коридор ~CF 1900–2400 — меняет характер работы ещё раз. Здесь почти не бывает «одна задача — один приём»: типичное условие собирается из двух-трёх известных кирпичей, и главная трудность не в том, чтобы вспомнить алгоритм, а в том, чтобы увидеть, какие именно кирпичи подходят и в каком порядке их сложить.

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

Обе задачи на него, но берут его с разных сторон. Первая — Дейкстра почти в чистом виде, зато с восстановлением самого маршрута, а не только его длины: это то место, где ошибаются чаще всего. Вторая показывает главный способ усложнить задачу, не меняя в алгоритме ни строчки: метрик оказывается две — метры и деньги, — и Дейкстра запускается дважды, поверх собственного результата.

Довести приём до состояния «пишу не задумываясь» стоит именно сейчас: дальше на «Пике» он будет появляться как готовая деталь внутри более сложных решений, без повторного объяснения.

---

Теория

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

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

Когда применять:

• в условии есть «минимальная стоимость пути», «минимальное время в дороге», «кратчайший маршрут», и рёбра имеют разный вес;
• все веса неотрицательные (отрицательное ребро ломает алгоритм — об этом ниже);
• размер графа — до сотен тысяч вершин и рёбер, то есть перебор путей и обход в ширину по «развёрнутым» рёбрам не проходят.

Как решать:

1. Завести массив dist — текущая известная оценка расстояния до каждой вершины; всё бесконечность, кроме старта (там ноль).
2. Положить в приоритетную очередь пару (0, старт).
3. Пока очередь не пуста: достать пару с наименьшим расстоянием. Если это расстояние больше уже записанного в dist — запись устарела, пропустить.
4. Иначе просмотреть все рёбра из этой вершины и, если через неё до соседа получается короче, обновить dist[сосед] и положить в очередь новую пару.

Мини-пример. Три вершины, рёбра 1–2 длиной 7 и 1–3 длиной 2, 3–2 длиной 3. Сначала dist = [0, ∞, ∞]. Достаём вершину 1: соседу 2 ставим 7, соседу 3 ставим 2. Достаём вершину 3 (она ближе): через неё до вершины 2 получается 2 + 3 = 5, что меньше семи, — обновляем. Достаём вершину 2 со значением 5. Пара (7, 2) тоже лежит в очереди, но когда до неё дойдёт черёд, 7 > dist[2] = 5, и она будет пропущена как устаревшая.

Это и есть ленивое удаление: вместо того чтобы уменьшать ключ уже лежащего в очереди элемента (стандартная куча так не умеет), мы кладём новую пару, а старую отбрасываем при извлечении. Именно поэтому строка «если достанутое расстояние больше записанного — пропустить» обязательна: без неё алгоритм остаётся правильным, но начинает разворачивать вершину по несколько раз.

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

Чтобы вывести сам маршрут, а не только его длину, заводят массив parent: в момент, когда dist[to] улучшается через вершину v, записывают parent[to] = v. Маршрут собирается с конца — от финиша по предкам до старта — и разворачивается.

Каркас приёма (граф g[v] — список пар «сосед, длина ребра»):

Где ошибаются в узнавании: видят слово «кратчайший» и запускают обход в ширину. Обход в ширину даёт кратчайший путь только когда все рёбра одинаковой длины — как только длины разные, он находит путь с минимальным числом рёбер, а не с минимальной суммой длин.

Сложность приёма: $O((n + m)\log n)$ с двоичной кучей.

Три обстановки, где Дейкстра — правильный ответ. Сам алгоритм один, но узнаётся он по-разному, и полезно держать в голове весь список:

1. Прямая. Дан граф, у рёбер разные положительные длины, спрашивают кратчайший путь или расстояния до всех вершин. Тут вопросов не возникает.
2. Вершины — это состояния. Граф в условии не нарисован, но его можно построить: вершина — «положение плюс какое-то маленькое состояние» (набор собранных предметов битовой маской, остаток от деления, номер использованного бонуса), ребро — переход между состояниями со своей ценой. Признак: в условии есть небольшой параметр, от которого зависит стоимость дальнейших ходов.
3. Второй слой поверх первого. Расстояния считаются дважды по разным метрикам: сначала «сколько метров», потом «сколько денег» или «сколько пересадок». Именно так устроена сегодняшняя вторая задача — и это самый частый способ усложнить Дейкстру, не меняя в ней ни строчки.

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

Что делать, если отрицательные веса всё-таки есть:

• отрицательные рёбра, но нет отрицательных циклов — алгоритм Форда-Беллмана за $O(nm)$;
• все веса равны — обычный обход в ширину за $O(n + m)$, очередь не нужна;
• веса только 0 и 1 — обход в ширину на деке: ребро веса 0 кладём в начало, веса 1 — в конец, тоже $O(n + m)$.

Последний вариант стоит запомнить отдельно: задачи вида «сколько рёбер придётся развернуть» часто решаются именно им, а не полноценной Дейкстрой.

Почему очередь с приоритетом, а не поиск минимума перебором. Наивная версия ищет ближайшую незакрытую вершину простым проходом по массиву: это $O(n^2)$ и на плотном графе даже быстрее кучи. Но при $n$ до $10^5$ и разреженном графе выигрывает куча — $O((n + m)\log n)$. Практическое правило: если рёбер сильно меньше, чем $n^2$, берут кучу; если граф почти полный, проще и быстрее массив.

Ленивое удаление. В классическом описании при улучшении метки нужно «уменьшить ключ» в очереди, но ни в питоновском heapq, ни в priority_queue такой операции нет. Вместо этого в кучу кладут новую запись, а старую распознают при извлечении по условию «расстояние из кучи больше текущего» и пропускают. Из-за этого в куче оказывается до $m$ записей вместо $n$ — на сложность это не влияет, а код упрощает.

С чем путают. Соседний инструмент — обход в ширину: он тоже находит «кратчайший» путь, но в смысле числа рёбер. Если длины разные, обход в ширину даёт неверный ответ; если одинаковые, Дейкстра даст верный, но с лишним множителем-логарифмом. Второй сосед — поиск минимального остова: там тоже жадно выбирают минимальное ребро, но задача другая (связать все вершины дешевле всего, а не дойти из одной в другую), и пути в остове кратчайшими не являются.

Сложность приёма: $O((n + m)\log n)$ с двоичной кучей.

---

Задача 1 — CF ~1900 — «Dijkstra?»

Что дано

Дан неориентированный взвешенный граф на n вершинах и m рёбрах. Нужно найти кратчайший путь между вершиной 1 и вершиной n — и вывести сам путь, то есть последовательность вершин. Если пути нет, вывести −1.

Формат ввода:

• Строка 1: два числа n и m ($2 \le n \le 10^5$, $0 \le m \le 10^5$).
• Каждая из следующих m строк: три числа a, b, w — концы ребра и его длина ($1 \le a, b \le n$, $1 \le w \le 10^6$).

Формат вывода: последовательность вершин кратчайшего пути от 1 до n через пробел, либо −1, если пути не существует.

Пример:

Ввод:
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

Вывод:
1 4 3 5

Разберём на примере

Нарисуем граф словами: из вершины 1 выходят рёбра в 2 (длина 2) и в 4 (длина 1); из 2 — в 5 (5) и в 3 (4); из 4 — в 3 (3); из 3 — в 5 (1).

Первое, что стоит проверить руками: путь с наименьшим числом рёбер — не ответ. Маршрут 1 → 2 → 5 состоит всего из двух рёбер и даёт длину $2 + 5 = 7$. А маршрут 1 → 4 → 3 → 5 длиннее по числу рёбер, но короче по сумме: $1 + 3 + 1 = 5$. Именно поэтому обход в ширину, который минимизирует количество шагов, здесь даст неправильный ответ.

Теперь проследим Дейкстру по шагам. В очереди лежат пары «расстояние, вершина»; жирным отмечено то, что извлекается на текущем шаге.

Обратите внимание на последнюю строку: пара (7, 5) осталась в очереди. Мы не удаляли её при улучшении вершины 5 — она просто была бы отброшена проверкой 7 > dist[5] = 5. Это ленивое удаление в чистом виде.

Теперь восстанавливаем маршрут. Предки: parent[5] = 3, parent[3] = 4, parent[4] = 1, parent[1] = 0 (старт). Идём с конца: 5, 3, 4, 1 — и разворачиваем: 1 4 3 5. Совпадает с ожидаемым выводом.

Идея решения

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

Почему это работает. Корректность Дейкстры держится на одном свойстве: когда вершина извлекается из очереди впервые, записанное для неё расстояние — окончательное. Причина в неотрицательности весов. Допустим, до вершины v существует более короткий путь, чем найденный. Этот путь где-то впервые выходит за пределы уже обработанного множества вершин — через некоторую вершину u, которая ещё в очереди. Тогда расстояние до u не больше длины всего этого пути (остаток пути неотрицателен), а значит и не больше dist[v]. Но раз мы извлекли v, а не u, то dist[v] — минимум в очереди, и значит dist[u] не меньше dist[v]. Обе оценки вместе означают, что «более короткий путь» короче не был.

Почему восстановление через предков корректно. Массив parent записывается только в момент реального улучшения dist[to]. Поэтому в конце для каждой достижимой вершины parent указывает на предпоследнюю вершину какого-то кратчайшего пути в неё. Поднимаясь по предкам, мы каждый раз строго уменьшаем расстояние (dist[parent[v]] < dist[v], потому что вес ребра положителен), значит зациклиться невозможно и подъём обязательно закончится в старте.

Почему не подойдут другие алгоритмы. Обход в ширину минимизирует число рёбер, а не сумму — на примере выше это уже видно. Алгоритм Беллмана — Форда даёт $O(nm) = 10^{10}$ операций. Наивная Дейкстра «искать минимум простым перебором массива» — $O(n^2) = 10^{10}$. Проходит только версия с приоритетной очередью.

Про типы. До $10^5$ рёбер по $10^6$ каждое — длина пути доходит до $10^{11}$, 32-битный тип переполняется.

Псевдокод

прочитать n, m, построить списки смежности (ребро добавить в обе стороны)

dist[v] = бесконечность для всех v, dist[1] = 0
parent[v] = 0 для всех v
очередь = { (0, 1) }

пока очередь не пуста:
    (d, v) = извлечь минимум
    если d > dist[v]: продолжить            // устаревшая запись
    если v == n: прервать                   // финиш закрыт, дальше не нужно
    для каждого ребра (v -> u, вес w):
        если d + w < dist[u]:
            dist[u] = d + w
            parent[u] = v
            положить (dist[u], u) в очередь

если dist[n] == бесконечность:
    вывести -1
иначе:
    путь = []
    v = n
    пока v != 0:
        добавить v в путь
        v = parent[v]
    развернуть путь и вывести

Код решения

Комментарии по реализации. Ноль выбран как маркер «предка нет», потому что вершины нумеруются с единицы — цикл подъёма while v: останавливается сам, без отдельной проверки на старт. Досрочный выход if v == n: break не обязателен для корректности, но экономит заметную часть работы на больших графах, где финиш оказывается близко. Восстановление пути сделано циклом, а не рекурсией: цепочка из $10^5$ вершин положила бы стек. Вывод собирается в одну строку — сто тысяч отдельных печатей заметно медленнее одной.

Проверка на примерах

Пример из условия: пошаговая таблица выше даёт dist[5] = 5 и предков parent[5] = 3, parent[3] = 4, parent[4] = 1. Подъём: 5 → 3 → 4 → 1, разворот: 1 4 3 5. Наш вывод: 1 4 3 5 — совпадает с ожидаемым.

Дополнительно прогоним решение на двух ситуациях, которых в условии нет, но которые обязаны отработать.

Граф без рёбер:

Ввод:
2 0

Вывод:
-1

Очередь опустошается сразу после извлечения (0, 1), dist[2] остаётся бесконечностью — выводим −1.

Две несвязанные части:

Ввод:
4 2
1 2 5
3 4 5

Вывод:
-1

Дейкстра доходит до вершины 2 и останавливается: до вершин 3 и 4 добраться нечем. dist[4] = ∞, ответ −1.

Крайние случаи

• m = 0. Рёбер нет вовсе, ответ сразу −1; циклы по спискам смежности не выполняются ни разу.
• Финиш недостижим. Проверка dist[n] == ∞ обязана стоять до восстановления пути — иначе подъём по предкам уйдёт в вершину без предка.
• Кратные рёбра между одной парой вершин. Лишние экземпляры безвредны: улучшить dist сможет только самый короткий из них, остальные не пройдут проверку nd < dist[u].
• Петля a = b. Даёт nd = d + w > d = dist[v], обновления не будет — обрабатывать отдельно не нужно.
• Путь из $10^5$ рёбер по $10^6$. Сумма $10^{11}$ — 64-битный тип обязателен, и в C++ бесконечность нельзя брать как LLONG_MAX: к ней в коде прибавляют вес.
• Граф-цепочка на $10^5$ вершин. Проверка того, что восстановление пути не рекурсивное.
• Ответ из одного ребра при n = 2. Путь 1 2 — вырожденный случай, на котором ломаются реализации, печатающие «путь без первой вершины».

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

1. Обход в ширину вместо Дейкстры. Даёт путь с минимальным числом рёбер: на примере из условия — 1 2 5 длиной 7 вместо 1 4 3 5 длиной 5.
2. Дейкстра за $O(n^2)$. Поиск минимума перебором массива на $10^5$ вершинах — $10^{10}$ операций.
3. Не пропускать устаревшие записи. Строка if d > dist[v]: continue — не украшение: без неё вершина разворачивается столько раз, сколько раз попала в очередь.
4. Считать расстояния в 32-битном типе. До $10^{11}$.
5. Добавлять ребро только в одну сторону. Граф неориентированный, и это легко упустить, потому что на маленьких примерах ответ часто всё равно получается верным.
6. Забыть развернуть путь. Подъём по предкам даёт маршрут от финиша к старту; без разворота вывод будет зеркальным.
7. Восстанавливать путь рекурсией. На цепочке из $10^5$ вершин это переполнение стека.
8. Выводить длину пути вместо самого пути. Здесь просят последовательность вершин — типичная потеря балла на невнимательности.

Сложность

Время: $O((n + m)\log n)$ — каждое ребро может добавить в очередь одну запись, извлечение стоит логарифм. Память: $O(n + m)$.

---

Задача 2 — CF ~1900 — «Volleyball»

Что дано

В городе n перекрёстков и m двусторонних дорог; у каждой дороги известна длина. На каждом перекрёстке i стоит машина, которая берёт фиксированную плату c[i] независимо от расстояния и готова везти не дальше чем на t[i] метров суммарно. Сесть в машину можно только на том перекрёстке, где она стоит; выйти — на любом другом, лишь бы суммарная длина поездки не превысила t[i]. Каждой машиной можно воспользоваться не больше одного раза.

Нужно добраться с перекрёстка x на перекрёсток y, потратив как можно меньше денег, или сообщить, что доехать нельзя.

Формат ввода:

• Строка 1: два целых числа n и m ($1 \le n \le 1000$, $0 \le m \le 1000$).
• Строка 2: два целых числа x и y — начальный и конечный перекрёстки.
• Далее m строк: три числа u, v, w — дорога между u и v длиной w ($1 \le w \le 10^9$). Дорог между парой перекрёстков может быть несколько, петель нет.
• Далее n строк: два числа t[i] и c[i] ($1 \le t_i, c_i \le 10^9$) — предельное расстояние и плата для машины с перекрёстка i.

Формат вывода: минимальная суммарная плата или -1, если доехать невозможно.

Пример 1:

Ввод:
4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7

Вывод:
9

Разберём на примере

Нарисуем город. Дороги: 1–2 длиной 3, 1–4 длиной 1, 2–4 длиной 1, 2–3 длиной 5. Едем из 1 в 3.

Машины: на перекрёстке 1 — не дальше 2 метров за 7 рублей; на 2 — не дальше 7 за 2; на 3 — не дальше 1 за 2; на 4 — не дальше 7 за 7.

Первое, что бросается в глаза: длина пути не влияет на цену. Платим мы за факт поездки, а расстояние важно только как ограничение — «дотянет машина или нет». Значит перед нами две совершенно разные метрики, и путать их нельзя: по дорогам считаются метры, по пересадкам — рубли.

Посмотрим, куда дотягивается каждая машина. Кратчайшие расстояния от перекрёстка 1: до 4 — один метр (прямая дорога), до 2 — два метра (через 4, потому что прямая дорога длиной 3 хуже), до 3 — семь метров. Машина с перекрёстка 1 везёт не дальше двух метров, значит из неё можно выйти на 4 или на 2.

От перекрёстка 2 расстояния такие: до 4 — один, до 1 — два, до 3 — пять. Предел этой машины семь метров, то есть она довезёт куда угодно, в том числе прямо до цели.

Теперь маршрут собирается сам: садимся на перекрёстке 1, платим 7 и выходим на перекрёстке 2 (два метра, укладываемся). Там садимся во вторую машину, платим 2 и едем до 3 (пять метров, укладываемся). Итого 9 рублей — совпадает с эталоном.

Проверим, что дешевле не выйдет. Единственный способ уехать с перекрёстка 1 — заплатить 7, других машин там нет. Дальше мы оказываемся либо на 2, либо на 4. С перекрёстка 4 машина стоит 7 рублей, с перекрёстка 2 — два. Значит минимум это 7 + 2 = 9.

И вот ключевое наблюдение. Мы дважды делали одно и то же — искали кратчайшие расстояния, — но на разных графах и с разной «длиной». Сначала по дорогам, чтобы понять, кто куда дотягивается. Потом по «поездкам», где ребро из i в j существует, если машина с i довезёт до j, а его вес — цена c[i]. Второй поиск — тоже Дейкстра, просто граф другой.

Идея решения

Алгоритм в одну фразу: запустить Дейкстру из каждого перекрёстка по дорожному графу, построить по её результатам граф поездок (ребро i → j весом c[i], если расстояние от i до j не превосходит t[i]) и запустить Дейкстру ещё раз — уже по нему, из x в y.

Почему нужен именно двойной запуск. Соблазнительно попробовать одну Дейкстру на исходном графе с какими-нибудь хитрыми весами, но это не работает: цена поездки не складывается из цен рёбер. Стоимость определяется тем, где мы пересаживаемся, а не тем, по каким дорогам едем. Поэтому дорожная сеть нужна только для одного вопроса — «дотягивается ли машина i до перекрёстка j», — и после того, как на него получены все ответы, дороги можно забыть.

Почему во втором графе снова Дейкстра. Задача на нём формулируется дословно как «кратчайший путь из x в y», где длина ребра — цена поездки, число положительное. Это ровно та обстановка, для которой алгоритм и предназначен. Обход в ширину не подойдёт: цены разные, и путь из двух дешёвых поездок бывает выгоднее одной дорогой.

Почему хватает n запусков. Ограничения тут подобраны так, что решение «в лоб» проходит: $n, m \le 1000$, значит n Дейкстр стоят $O(n \cdot m \log n)$ — порядка $10^7$ операций. Это тот редкий случай на «Пике», когда не нужно ничего придумывать сверх аккуратной реализации, и полезно уметь такое распознавать: прежде чем изобретать хитрость, стоит посчитать, не проходит ли прямой подход.

Про «каждой машиной не больше одного раза». Это ограничение можно спокойно игнорировать. Кратчайший путь в графе поездок не проходит через одну вершину дважды: если бы проходил, кусок между двумя посещениями можно было бы выкинуть, и цена только уменьшилась бы. Так что условие выполняется само собой.

Псевдокод

прочитать n, m, x, y, дороги, параметры машин

// первый слой: докуда дотягивается каждая машина
для i от 1 до n:
    dist = Дейкстра(i) по дорожному графу
    для j от 1 до n, j != i:
        если dist[j] <= t[i]:
            добавить в граф поездок ребро i -> j весом c[i]

// второй слой: тот же алгоритм, но веса — деньги
best = Дейкстра(x) по графу поездок
вывести best[y], либо -1, если недостижимо

Код решения

Комментарии по реализации. Обе метрики 64-битные, и по разным причинам: расстояния складываются из тысячи рёбер по $10^9$ (до $10^{12}$), цены — из тысячи поездок по $10^9$ (столько же). В 32-битном типе не помещается ни то, ни другое. Функция Дейкстры написана одна и вызывается для обоих графов — это не экономия строк, а способ не завести две почти одинаковые функции и не перепутать в них веса. Граф поездок хранится списками смежности и в худшем случае содержит около миллиона рёбер: для $n = 1000$ это допустимо по памяти, но строить его матрицей уже не стоит. Обратите внимание, что кратные дороги между одной парой перекрёстков просто добавляются в список как есть — Дейкстра сама выберет короткую.

Проверка на примерах

Пример 1: четыре перекрёстка, едем из 1 в 3.

Первый слой — кратчайшие расстояния по дорогам и что из них следует:

Обратите внимание на расстояние от 1 до 2: прямая дорога длиной 3 проигрывает обходу через перекрёсток 4 — единица плюс единица. Ровно из-за этого машина с перекрёстка 1, у которой предел два метра, до перекрёстка 2 всё-таки дотягивается. Решение, которое смотрит только на прямые дороги, здесь ошибётся.

Второй слой — Дейкстра по графу поездок из вершины 1:

Наш вывод: 9 — совпадает с ожидаемым.

Крайние случаи

• x = y. Ехать никуда не надо, ответ 0. Дейкстра даёт это автоматически: стартовое расстояние нулевое.
• m = 0. Дорог нет вовсе; ни одна машина никуда не дотягивается. Ответ 0, если x = y, иначе −1.
• Цель недостижима по дорогам. Расстояние остаётся бесконечным, ребро в графе поездок не появляется, второй запуск возвращает бесконечность — печатаем −1.
• Машина дотягивается до цели прямо со старта. Ответ равен c[x]; проверка, что мы не заставляем делать лишнюю пересадку.
• Предел ровно равен расстоянию. Сравнение обязано быть нестрогим: dist[j] <= t[i]. Строгое неравенство теряет ровно те тесты, где всё «впритык».
• Несколько дорог между одной парой перекрёстков. Штатная ситуация: лишние рёбра просто никогда не выбираются.
• Максимальный размер ($n = m = 1000$, все перекрёстки связаны). Граф поездок вырастает до миллиона рёбер — проверка на то, что решение не строит матрицу расстояний целиком и не пересчитывает Дейкстру внутри цикла по j.

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

1. Считать, что цена зависит от расстояния. Самая частая ошибка чтения условия: плата фиксированная, расстояние — только ограничение.
2. Строить граф поездок по прямым дорогам. Машина может доехать до перекрёстка через промежуточные, поэтому нужны именно кратчайшие расстояния, а не список соседей. В разобранном примере на этом теряется правильный ответ.
3. Строгое сравнение с пределом. dist[j] < t[i] вместо <= — тихая потеря маршрутов, которые укладываются ровно в предел.
4. 32-битные типы. И расстояния, и цены доходят до $10^{12}$.
5. Пытаться уложиться в одну Дейкстру. Метрики две и они несовместимы; попытка смешать их в одном весе даёт неверный ответ на первом же тесте, где длинный путь дешевле короткого.
6. Считать ограничение «каждой машиной один раз» существенным. Оно выполняется само: кратчайший путь не проходит через вершину дважды.
7. Забыть про −1. Недостижимость — отдельная ветка вывода, а не ноль.

Сложность

Время: $O(n \cdot (n + m)\log n)$ — по одному запуску Дейкстры из каждой вершины плюс финальный запуск по графу поездок, в котором до $n^2$ рёбер. При $n, m \le 1000$ это порядка $10^7$ операций. Память: $O(n^2)$ в худшем случае — столько рёбер может оказаться в графе поездок.

---

Самостоятельная тренировка

Все четыре — на сегодняшний приём: в каждой нужен именно поиск кратчайших расстояний с приоритетной очередью, отличается только то, что считать вершиной и что весом.

• Codeforces 1725M «Moving Both Hands» (~CF 1800) — две фишки стоят в вершине 1 и в вершине i; за ход можно двигать любую из них по ориентированному ребру, платя его вес; для каждой i нужно минимальное время встречи. Подсказка: запустите алгоритм по исходному графу и по графу с развёрнутыми рёбрами, а потом аккуратно совместите два результата.
• Codeforces 1846G «Rudolf and CodeVid-23» (~CF 1900) — состояние описывается набором из не более чем десяти признаков, каждое «лекарство» снимает одни признаки и добавляет другие за известное время; нужно минимальное время прийти к пустому набору. Вторая обстановка из теории в чистом виде: вершина — битовая маска, ребро — применение лекарства.
• Codeforces 449B «Jzzhu and Cities» (~CF 2000) — кроме обычных дорог есть прямые маршруты из столицы в отдельные города; нужно удалить как можно больше таких маршрутов, не увеличив ни одно кратчайшее расстояние от столицы. Подсказка: посчитайте расстояния один раз, а затем для каждого маршрута решите, обязателен ли он, — и не забудьте про случай, когда в один город ведут два одинаковых маршрута.
• Codeforces 1650G «Counting Shortcuts» (~CF 2100) — нужно посчитать количество путей, длина которых превышает кратчайшую не более чем на единицу. Самая сложная в наборе: вершиной становится пара «вершина графа плюс превышение (0 или 1)», и вместе с расстояниями приходится аккуратно считать количества.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Первая тренировка «Пика» позади. Дейкстра дальше пойдёт как готовая деталь, и возвращаться к её устройству мы не будем — если сегодня каркас писался с подглядыванием, стоит воспроизвести его по памяти прямо сейчас, пока свежо. И отдельно стоит запомнить вторую задачу: не саму её, а ход мысли «метрик в условии две, значит и запусков будет два». Это едва ли не самый частый способ, которым знакомый алгоритм прячут в незнакомой обёртке.

На следующей тренировке характер «Пика» проявится в полную силу: там не будет алгоритма как такового — будет наблюдение про минимум отрезка, из которого решение выводится в несколько строк.