Подразделы

Другие разделы

Дата и время

13/03/2025 18:07:51

Авторизация

946. Дорожная реформа

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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}$ .

Пример ввода

Пример вывода

1.4142

Источник: РГУ им. И.Канта, осенний командный турнир, 2007

03/07/2008	Лето 2008 дорешивание ( 3D)
07/07/2008	Лето 2008 - 3 (D)
25/11/2014	Занятие 12 (C)
12/07/2016	Лето 2016 - 8 (D)
05/03/2023	«Базовая олимпиадная подготовка» (second level) - Остовные деревья (проводит novink) (A)
16/09/2024	Остовные деревья, СНМ (проводит BOGAT) (D)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

946. Дорожная реформа

Дорожная реформа