Снегоуборщик Бишкека
В Бишкеке после снегопада снегоуборочная машина должна проехать по каждой из 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.
Подсказка
Задача китайского почтальона: граф, в котором все степени чётны и он связен, имеет эйлеров цикл (теорема Эйлера). Значит, нужно дешевле всего «удвоить» пути между вершинами нечётной степени, разбив их на пары.
Комментарии