Falla de Energía.
¡Una tormenta eléctrica ha destruido algunos de los cables de la malla eléctrica del Granja! El Granjero Juan tiene un mapa de todos los puntos de conexión , los cuales están numerados convenientemente y ubicados en coordenadas enteras , .
Algunos cables conectan pares de puntos de conexión y .
El necesita llevar energía del punto 1 al punto (lo cual implica que alguna serie de cables pueden ir del punto 1 al punto , probablemente a través de un conjunto intermedio de puntos).
Dadas las ubicaciones de los puntos y una lista de los cables que permanecieron, determine la longitud mínima de cables requeridos para restaurar la conexión eléctrica de tal manera que la electricidad pueda ir del punto 1 al punto . Ningún cable puede ser mayor que un número real .
Como ejemplo, abajo en la izquierda está un mapa de los 9 puntos y 3 cables después de la tormenta. Para esta tarea, = 2.0. El mejor conjunto de cables a añadir sería conectar los puntos 4 y 6 y también los puntos 6 y 9.
Después de la tormenta Reconexión óptima
3 . . . 7 9 . . . . . 3 . . . 7 9 . . . . .
/
2 . . 5 6 . . . . . . 2 . . 5 6 . . . . . .
/
1 2-3-4 . 8 . . . . . 1 2-3-4 . 8 . . . . .
| |
0 1 . . . . . . . . . 0 1 . . . . . . . . .
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
La longitud total es entonces 1.414213562 + 1.414213562 = 2.828427124 .
Entrada
- Línea Dos enteros separados por espacio: y .
- Línea Un solo número real: .
- Líneas Cada línea contiene dos enteros separados por espacios: y
- Líneas Dos enteros separados por espacios: y .
Ejemplo de Entrada
9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4
Detalles de la Entrada
Precisamente los mostrado en el diagrama anterior.
Salida
- Línea Un solo entero en una sola línea. Si restaurar la conexión es imposible, dé como salida –1. En otro caso, dé como salida un solo entero que es 1000 veces el costo mínimo total de restaurar la electricidad. No ejecute ningún redondeo; trunque el producto resultante.
Ejemplo de Salida
2828
Detalles de la Salida
Como en el diagrama anterior.
Comments