Снегоуборщик Бишкека


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В Бишкеке после снегопада снегоуборочная машина должна проехать по каждой из m улиц хотя бы один раз (улицы двусторонние, по любой можно проезжать сколько угодно раз) и вернуться в гараж. Перекрёстков n, улица i соединяет перекрёстки u[i] и v[i] и имеет длину w[i]; бывают несколько улиц между одними и теми же перекрёстками и улицы-петли. Гараж стоит на перекрёстке 1, все улицы достижимы из гаража.

Рисунок

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

Входные данные

В первой строке — n и m (1 ≤ n ≤ 2 · 10⁴, 1 ≤ m ≤ 10⁵). В каждой из следующих m строк — три целых числа u v w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁶).

Выходные данные

Выведите длину кратчайшего маршрута.

Пример 1

Вход:

4 5
1 2 4
2 3 1
3 4 2
4 1 3
1 3 4

Выход:

18

Пояснение

Нечётное число улиц подходит к перекрёсткам 1 и 3. Кратчайший путь между ними — улица 1–3 длины 4, её придётся проехать дважды. Ответ: сумма длин всех улиц 14 плюс 4, то есть 18.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов m ≤ 10.

Подсказка

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


Комментарии

Еще нет ни одного комментария.