Nuevas carreteras


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

El alcalde de tu ciudad ha creado barrios residenciales nuevos. El quiere conectar los barrios nuevos con carreteras de tal manera que el pueda viajar de cualquier barrio a cualquiera otro a través de carreteras; hay carreteras que ya conectan algunos de los barrios.

Cada uno de los N (1 \leq N \leq 1,000) barrios (convenientemente numerados 1..N) está representado por una posición (X_i, Y_i) en el plano (0 \leq X_i \leq 1,000,000; 0 \leq Y_i \leq 1,000,000). Dadas las M carreteras pre existentes (1 \leq M \leq 1,000) como pares de barrios conectados, ayude al alcalde a determinar la menor longitud de carreteras adicionales que él debe construir para conectar todos los barrios.

Formato de entrada:

Línea 1: Dos enteros separados por espacio: N y M.

Líneas 2..N+1: Dos enteros separados por espacio: X_i y Y_i

Líneas N+2..N+M+2: Dos enteros separdos por espacio: i y j indicando que ya hay una carretera que conecta los barrios i y j.

Formato de salida:

La menor longitud de senderos adicionales requeridos para conectar todos los barrios impresa sin redondear con dos decimales. Este seguro de calcular la distancia usando números flotantes de 64 bits.

Ejemplo de entrada

4 1
1 1
3 1
2 3
4 3
1 4

Ejemplo de salida:

4.00

Explicacion de la entrada:

Los barrios 1 y 4 ya están conectados por un sendero. Conectar los barrios 1 y 2 con un sendero que tiene 2.00 unidades de longitud, luego conectar los barrios 3 y 4 con un sendero que tiene 2.00 unidades de longitud. Esto es lo mejor que podemos hacer, y da un total de 4.00 unidades de longitud.


Comments

There are no comments at the moment.