Задача A: Кольцевая
Это довольно простая задача - мы имеем цикл, можем ориентировать его в одну из 2х сторон. Осталось посчитать стоимость ориентации цикла в обе стороны и выбрать меньшую.
Есть небольшой трюк - можно посчитать стоимость только для одной ориентации. Стоимость другой - это суммарная стоимость всех ребер минус стоимость первой
Полный текст и комментарии »