Обсуждение @ 1272. Метро не в Екатеринбурге @ Timus Online Judge

Online Judge

Задачи

Авторы

Соревнования

SerailHydra Method [2] // Задача 1272. Метро не в Екатеринбурге 10 ноя 2007 17:57

You can consider that the cost of the tunnel is 1, and the bridge is 24000. Then it becomes a MST problem.

Erop [USU] Re: Method // Задача 1272. Метро не в Екатеринбурге 6 апр 2010 20:22

would be better to make weight tunnel 0, the weight of the bridge 1, and the answer is weight of minimal spanning tree

Artem Khizha [DNU] Re: Method // Задача 1272. Метро не в Екатеринбурге 22 июл 2010 00:00

Your idea is interesting, but weird a bit. :)
It can be solved with DFS easily. Moreover, you even don't need to know anything about bridges.