Самый короткий круг
Курьер-велосипедист разминается перед сменой: он хочет проехать круг и вернуться туда, откуда начал, не проезжая ни одну улицу дважды и не заезжая дважды ни на один перекрёсток. Чем короче круг, тем лучше: смена скоро. Помогите найти длину самого короткого такого круга. Начинать можно с любого перекрёстка.
Круг должен проходить хотя бы через три разных перекрёстка: проехать по улице туда и тут же обратно — не круг. Два теста — настоящие улицы: по 150 перекрёстков центра Алматы из OpenStreetMap около площади Республики и около Зелёного базара, длины в метрах. В настоящих данных самый короткий круг оказывается вовсе не кварталом, а треугольником из коротких кусков улиц у перекрёстка.
Вход
В первой строке n и m (1 ≤ n ≤ 150, 0 ≤ m ≤ n(n − 1)/2) — число перекрёстков и улиц. Дальше m строк a b w: улица между перекрёстками a и b длиной w, по ней можно ехать в обе стороны (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ w ≤ 10⁶). Между двумя перекрёстками не больше одной улицы.
Выход
Длину самого короткого круга или -1, если кругов нет.
Примеры
Пример 1
5 7 1 2 3 2 3 3 3 1 3 3 4 1 4 5 1 5 1 1 1 4 5
6
Пример 2
4 3 1 2 7 2 3 2 2 4 9
-1
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Круг — это ребро (u, v) плюс путь из v обратно в u. Почему нельзя просто взять кратчайший путь из v в u из таблицы Флойда — Уоршелла?
2Подсказка 2
Пусть k — вершина круга с наибольшим номером. Какие вершины лежат на остальной части круга? И что в этот момент знает таблица алгоритма?
3Идея
Кратчайший путь из v в u часто и есть само ребро (v, u), и «круг» выходит поездкой туда и обратно. Нужно запретить пути проходить через вершины круга, и Флойд — Уоршелл даёт такой запрет даром. Возьмём в круге вершину k с наибольшим номером и её соседей по кругу i и j. Остаток круга — путь из i в j, все вершины которого меньше k. Ровно такие пути и лежат в таблице перед шагом k. Значит, перед шагом k проверим все пары i < j < k: d[i][j] + w[j][k] + w[k][i].
4Разбор
Заводим две таблицы: w — сами улицы (бесконечность, если улицы нет) и d — таблица алгоритма, вначале равная w. Для каждого k по порядку: сначала перебираем пары i < j < k, у которых есть улицы в k, и обновляем ответ суммой d[i][j] + w[j][k] + w[k][i]; потом делаем обычный шаг алгоритма через k.
Почему это всегда настоящий круг. Перед шагом k путь из i в j идёт только через вершины с номерами меньше k, поэтому k на нём нет; i ≠ j, и кратчайший путь при положительных длинах не повторяет вершин. Добавив k, получаем круг хотя бы из трёх вершин. Почему найдётся самый короткий. Возьмём самый короткий круг и его вершину k с наибольшим номером, соседей i и j. Остаток круга — путь из i в j через вершины меньше k, и d[i][j] перед шагом k не длиннее его. Значит, проверка на шаге k найдёт сумму не больше длины этого круга, а меньше быть не может — за суммой стоит настоящий круг.
Порядок «проверить, потом обновить» здесь главный. Если проверять после шага, путь из i в j может уже идти через k, и сумма опишет поездку i → k → j → k → i по одним и тем же улицам. На первом примере такое решение ответит 4 вместо 6.
Для одного графа можно иначе: для каждой улицы (u, v) убрать её и найти Дейкстрой кратчайший путь из u в v. Это O(m · m log n) — для плотного графа хуже, чем O(n³).
4+Решение
5Сложность
O(n³) времени: шаги алгоритма — n³, проверки — около n³/6. Память O(n²) на две таблицы.
6Типичные ошибки
- Проверка после шага. Ответ меньше настоящего: круг проезжает улицы дважды — первый пример.
- Кратчайший путь между концами улицы. Без запрета это и есть сама улица, ответ — удвоенная самая короткая улица.
- Круг из двух вершин. Туда и обратно по одной улице — не круг, поэтому i ≠ j.
- Нет кругов. Граф — дерево или лес: ответ
-1, восьмой тест.