El ayuntamiento de Villabajo de Arriba, dada la explosión
demográfica que sufrió el pueblo con motivo de la nevada que lo
dejó incomunicado y sin luz durante una semana, ha decidido construir
una red metropolitana que una diversas urbanizaciones y barrios de nueva construcción.
Para ello, se dispone del listado de estaciones a construir y también
del coste de construcción de tramos bidireccionales entre diversos pares
de estaciones (no necesariamente todos, pues la existencia de arroyos, desniveles
y ruinas arqueológicas hace inviable la unión directa de algunas
estaciones). Se pide la construcción de un programa que determine los
tramos necesarios para unir todas las estaciones con el coste mínimo
de construcción de la red metropolitana. Eventualmente, puede ser imposible
construir dicha red, si con los tramos proporcionados existen estaciones desconectadas;
en este caso, el programa debe detectar la situación y dar aviso.
Entrada
Residente en el fichero de caracteres "REDM.DAT":
Línea 1: número N de estaciones, mediante un único
carácter que representa un entero entre 1 y 9
Línea 2: número M de tramos, mediante uno o dos caracteres que
representan un número entero entre 1 y 99
Líneas de la 3 a la N+2: cada una de estas líneas contiene una
única palabra formada exclusivamente por letras minúsculas (y
sin signos de puntuación, es decir, ni acentos ni similares), sin blancos
ni otro tipo de caracteres antes de la primera letra ni después de la
última. Las palabras tienen un máximo de 20 letras. Estas palabras
representan los nombres de las estaciones. Puede asumirse que estas líneas
no contendrán palabras repetidas.
Líneas N+3 a N+M+3: cada una de estas líneas tiene el formato:
estación estación coste
donde estación es alguna de las palabras que aparecieron en el grupo
anterior de líneas (es decir, un nombre válido de estación),
y coste es uno o dos caracteres que representan un número entero entre
1 y 99. Los tres componentes están separados por un único blanco,
y no hay blancos ni otro tipo de caracteres al inicio o final de línea.
Cada una de estas línea representa el coste de construcción de
un tramo; los tramos son bidireccionales, por lo que el orden de aparición
de las estaciones en una línea del fichero es irrelevante. Puede asumirse
que no hay tramos repetidos.
Salida
A guardar en el fichero de caracteres "REDM.OUT": un
número indeterminado de líneas, cada una de ellas con el formato:
estación estación
tal que la primera estación sea alfabéticamente menor que la segunda,
las estaciones estén separadas por un único blanco y no existan
blancos al inicio o final de línea. Además, las líneas
estarán ordenadas alfabéticamente según la primera estación;
en caso de empate, se considera también el orden alfabético por
la segunda estación. La salida representa pues los tramos que forman
parte de la solución. En caso que no haya sido posible construir la red
(es decir, si hay estaciones que no pueden conectarse), en el fichero aparecerá
una única línea que contenga la palabra IMPOSIBLE (en mayúsculas
y sin blancos ni otro tipo de caracteres antes ni después). En el caso
de existir solución, puede asumirse que ésta es única.
Ejemplo de entrada
4
5
mercado
puertonuevo
casasricas
casasbaratas
mercado puertonuevo 5
mercado casasricas 12
casasricas casasbaratas 8
puertonuevo casasricas 10
puertonuevo casasbaratas 20
Ejemplo de salida
casasbaratas casasricas
casasricas puertonuevo
mercado puertonuevo |
