Задача №112844. Туризм
Царь Байтазар убежден, что полная туристических достопримечательностей Байтазария должна привлечь множество туристов, и они должны тратить деньги, помогая заполнить королевскую казну. Тем не менее, этого не происходит. Король поручил своим советникам разобраться в этом вопросе. Оказалось, что причина низкой популярности царства среди иностранцев - недостаточно развитая сеть автомобильных дорог.
Стоит отметить, что в Байтазарии n городов, и m двусторонних дорог, каждая из которых соединяет два различных города. Дороги ведут через тоннели и эстакады. Поэтому не гарантируется, что из каждого города можно попасть в каждый.
Советник отметил, что нынешняя сеть автомобильных дорог не позволяет проводить какие-либо длительные поездки. Начиная тур в любом из городов, невозможно посетить более 10 городов, не посетив хотя бы один город два раза.
Из-за отсутствия средств, на строительство новых дорог, Байтазар решил построить в Байтозарии сети туристических информационных центров (ТИЦ), в которых надлежащим образом обученный персонал рекламируют преимущества быстрых поездок. Для каждого города, ТИЦ должен быть в этом городе или в одном из городов, соединенных дорогой с ним напрямую. Для каждого города, известна стоимость построить ТИЦ в этом городе. Помогите Байтазару найти самый дешевый способ построить сеть ТИЦ.
Первая строка стандартного ввода содержит два целых числа (2 ≤ n ≤ 20000, 0 ≤ m ≤ 25000) разделенных одним пробелом, обозначающее количество городов и дорог в Байтозарии. Города пронумерованы от 1 до n. Вторая строка содержит n целых чисел c1, c2,...,cn (0 ≤ ci ≤ 10000), разделенных пробелами; число представляет собой затраты на строительство ТИЦ в городе номер i.
Далее следует описание дорог в Байтfзарии. В i-й из следующих m строк два целых числа, ai, bi (1 ≤ ai < bi ≤ n), разделенные одним пробелом, ai соединено с bi ребром. Между каждой парой городов существует не более одной дороги.
Если ваша программа правильно работает на тестах, где \(n \le 20\) вы получите 20 баллов.
Ваша программа должна вывести одно целое число: суммарную стоимость строительства всех ТИЦ.
6 6
3 8 5 6 2 2
1 2
2 3
1 3
3 4
4 5
4 6
7
В примере из условия ТИЦ должны быть построены в городах 1, 5, 6 с общей стоимостью(3 + 2 + 2) 7.