НачалоПодразделы
Другие разделы
| 943. Овцы |
| 944. Подарок |
| 945. Укладка плитки |
| 947. Судоку |
| 948. Путешествие жука |
| 949. Сочинитель палиндромов |
| 950. Число e |
| 951. Спички |
| 952. Клуб писателей |
| 953. Movies |
Дата и время
06/12/2025 04:22:13
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
