Submeter | Todas submissőes | Melhores | Voltar |
PWRFAILU - Power Failure |
Points: 350
A vicious thunderstorm has destroyed some of the wires of the farm's electrical power grid! Farmer John has a map of all N (2 <= N <= 1,000) of the powerpoles, which are conveniently numbered 1..N and located on integer plane coordinates x_i,y_i (-100,000 <= x_i <= 100000; -100,000 <= y_i <= 100,000).
Some W (1 <= W <= 10,000) power wires connect pairs of power poles Pi and Pj (1 <= Pi <= N; 1 <= Pj <= N).
He needs to get power from pole 1 to pole N (which means that some series of wires can traverse from pole 1 to pole N, probably through some intermediate set of poles).
Given the locations of the N poles and the list of remaining power wires, determine the minimum length of power wire required to restore the electrical connection so that electricity can flow from pole 1 to pole N. No wire can be longer than some real number M (0.0 < M <= 200,000.0).
As an example, below on the left is a map of the 9 poles and 3 wires after the storm. For this task, M = 2.0. The best set of wires to add would connect poles 4 and 6 and also poles 6 and 9.
After the storm Optimally reconnected 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
The total length is then 1.414213562 + 1.414213562 = 2.828427124 .
Input
- Line 1: Two space-separated integers: N and W
- Line 2: A single real number: M
- Lines 3..N+2: Each line contains two space-separated integers: x_i and y_i
- Lines N+3..N+2+W: Two space-separated integers: Pi and Pj
Output
- Line 1: A single integer on a single line. If restoring connection is impossible, output -1. Otherwise, output a single integer that is 1000 times the total minimum cost to restore electricity. Do not perform any rounding; truncate the resulting product.
Example
Input: 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 Output: 2828
Input details
Just as in the diagram above.
Output details
As above.
Adicionado por: | Wanderley Guimarăes |
Data: | 2008-10-24 |
Tempo limite: | 0.200s-0.400s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Origem: | USACO October 2008 Qualifying Round |