Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
946. Дорожная реформа
Минимальное остовное деревоОлимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 3D) |
| 07/07/2008 | Лето 2008 - 3 (D) |
| 25/11/2014 | Занятие 12 (C) |
| 12/07/2016 | Лето 2016 - 8 (D) |
| 17/10/2025 | ЦОП2: остовные деревья, СНМ (проводит BOGAT) (D) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мудрый правитель Флатляндии затеял дорожную реформу. В его плоской стране есть `n` городов,
заданных своими координатами (`x_i,\ y_i`), `i\ =\ 1\ …\ n`, а также `m` дорог, соединяющих города. Правитель
хочет построить некоторые дополнительное число дорог (возможно, нулевое), так чтобы из любого
города можно было доехать в любой другой, двигаясь по дорогам. При этом сумма длин построенных
дорог должна быть минимально возможной.
Ввод
В первой строке входного файла записаны числа `n` и `m` (`1\ ≤\ n\ ≤\ 100`). В последующих `n` строках
содержатся координаты (`x_i,\ y_i`) городов, по одной паре в строке. Координаты представляют собой
целые числа, не превышающие по модулю `10^4`. Затем следуют `m` строк, описывающих дороги, по
одной в строке. Каждая дорога задается указанием пары номеров городов, которые она соединяют.
Вывод
В выходной файл выведите одно число – сумму длин вновь построенных дорог с точностью `10^{-4}`.
Пример ввода
3 1 1 1 3 1 2 2 1 3
Пример вывода
1.4142
