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

Задача

Таблица между станциями

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

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

Один из тестов — кусок улиц Алматы вокруг площади Республики с весами из статьи: энергия электромобиля, у спусков она отрицательна.

Вход

В первой строке — число вершин n, дуг m и станций k (1 ≤ n ≤ 600, 0 ≤ m ≤ 3000, 1 ≤ k ≤ 50). Дальше m строк u v w — дуга из u в v веса w, |w| ≤ 106; петли и кратные дуги возможны. В последней строке — k различных номеров станций.

Выход

k строк по k чисел: на месте (i, j) — вес кратчайшего пути из i-й станции в j-ю или «*», если пути нет. На диагонали — 0.

Примеры

Пример 1

Вход
4 5 3
1 2 1
1 3 3
3 2 -5
2 4 1
3 4 6
1 2 4
Выход
0 -2 -1
* 0 1
* * 0

Пример 2

Вход
5 4 4
1 2 3
2 3 -2
3 1 4
4 5 -7
1 3 4 5
Выход
0 1 * *
4 0 * *
* * 0 -7
* * * 0

Ограничения

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

Разбор

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

1Подсказка 1

Беллман — Форд от каждой станции — это k·n·m, до 9·107 релаксаций; Флойд — Уоршелл — n3 = 2·108. Обоим на Python тесно. Дейкстра от каждой станции был бы быстрым, но веса отрицательные — и уже первый пример это ломает. Можно ли сделать веса неотрицательными?

2Подсказка 2

Добавьте вершину, из которой в каждую ведёт дуга веса 0, и посчитайте от неё расстояния Беллманом — Фордом. Что можно сказать о w(u, v) + δ(u) − δ(v)?

3Идея

Алгоритм Джонсона. Расстояния δ от добавленной вершины удовлетворяют δ(v) ≤ δ(u) + w(u, v), поэтому приведённые веса w + δ(u) − δ(v) неотрицательны. Вес любого пути из s в t при этом меняется на δ(s) − δ(t) — на одно и то же число для всех путей, так что кратчайшие пути те же. Дейкстра от каждой станции на приведённых весах и обратный пересчёт: расстояние минус δ(s) плюс δ(t). Добавленную вершину строить не нужно: достаточно начать Беллмана — Форда со всех δ, равных нулю.

4Разбор

В первом примере из вершины 1 в вершину 2 ведёт прямая дуга веса 1, но путь 1 → 3 → 2 стоит 3 − 5 = −2. Дейкстра без перевзвешивания извлекает вершину 2 с весом 1 раньше, чем вершину 3, и больше её не трогает. Беллман — Форд со всеми δ, равными нулю, за один раунд находит δ = (0, −5, 0, −4), а на втором ничего не меняет. Приведённые веса: 1 → 2 — 1 + 0 − (−5) = 6, 1 → 3 — 3, 3 → 2 — −5 + 0 − (−5) = 0, 2 → 4 — 1 − 5 + 4 = 0, 3 → 4 — 6 + 0 + 4 = 10; отрицательных нет. Дейкстра из вершины 1 находит до вершины 2 путь через вершину 3 весом 3, и обратный пересчёт даёт 3 − 0 + (−5) = −2. До вершины 4 — 3 − 0 + (−4) = −1.

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

Беллман — Форд — O(n·m), до 1,8·106 релаксаций, и в шестом тесте, где цепочка перечислена с конца, ему действительно нужны почти все n раундов. Дальше k запусков Дейкстры по O(m log n). Всё вместе — несколько миллионов действий.

6Типичные ошибки
  • Дейкстра на исходных весах. Первый пример.
  • Забыть обратный пересчёт. Расстояние в приведённых весах — не ответ: нужно вычесть δ(s) и прибавить δ(t).
  • Циклы нулевого веса. Они разрешены — седьмой тест; Дейкстра с отметкой «уже извлечена» на них не зацикливается.
  • Недостижимые станции. Беллман — Форд от добавленной вершины даёт конечные потенциалы всем вершинам, но Дейкстра от станции доходит не до всех — тогда в ответе «*».

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

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