|
|
2099 - Picnic Planning |
||||
|
|
|
||||
La contorsión Hermanos son un famoso conjunto de payasos de circo, conocido mundialmente por su increíble capacidad para meter un número ilimitado de ellos, incluso en el más pequeño vehículo. Durante la temporada baja, al igual que los hermanos se reúnen para una reunión anual contorsionistas en un parque local. Sin embargo, los hermanos no sólo están ajustados con respecto a pequeños sectores, pero con dinero y, por lo que tratar de encontrar la manera de llegar a todos a la parte que minimiza el número de millas que en todos los coches (por lo tanto, el ahorro de gas, el desgaste y lacrimógenos, etc.) Para ello, están dispuestos a meterse a sí mismos en el menor número de vehículos necesarios para reducir al mínimo el número total de kilómetros puestos en todos sus coches juntos. Esto a menudo da lugar a muchos hermanos conduciendo a la casa de un hermano, dejando a todos, pero un coche allí y acumulan en el otro al resto. Existe una limitación en el parque, sin embargo: el estacionamiento en el sitio de picnic puede celebrar sólo un número limitado de vehículos, por lo que debe incluirse en el cálculo miserable. Asimismo, debido a un derecho de entrada al parque, una vez que el coche de cualquier hermano llega al parque y está ahí para quedarse, si él no deja sus pasajeros y, luego, sale a recoger a otros hermanos. Ahora, por medio de su clan circo, la solución de este problema es un reto, por lo que se deja a usted para escribir un programa para resolver su problema de minimización el kilometraje.
La entrada comienza con un solo número entero positivo en una línea por sí mismo que indica el número de los casos siguientes, cada uno de ellos, tal como se describe a continuación. Esta línea es seguida por una línea en blanco, y también hay una línea en blanco entre dos entradas consecutivas.
Cada caso constará de un ejemplo de problema La primera línea contendrá un solo número entero n que indica el número de conexiones de la autopista entre hermanos o entre hermanos y el parque. Las siguientes n líneas contienen una conexión por línea, de forma distinta como nombre1 nombre2, donde nombre1 y nombre2 son o bien los nombres de dos hermanos o la palabra “parque” y un hermano de nombre (tanto en orden), y distribución es entera y es la distancia entre ellos. Estas vías serán todas de 2 tipos vías y distintos, será siempre positivo. El máximo número de hermanos será 20 y la longitud máxima de cualquier nombre será de 10 caracteres. Seguidamente de las N líneas será una última línea que contiene un entero s, que especifica el número de coches que caben en el estacionamiento del sitio de picnic. Usted puede asumir que existe un camino de cada hermano a la casa del parque y que una solución para cada problema instancia.
Para cada caso de prueba, la salida debe seguir la siguiente descripción. Los resultados de dos casos serán separados por una línea en blanco.
Para cada caso de prueba, la salida debe constar de una sola forma de línea.
Total de millas manejada: xxx
Donde xxx es el número total de millas por todos los los conches de los hermanos.
Sample Input
2 10Alphonzo Bernardo 32Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3
10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43Bernardo Park 19
Bernardo Clemenzi 82Clemenzi Park 65
Clemenzi Herb 90Clemenzi Eduardo 109Park Herb 24Herb Eduardo 791
Sample Output
Total miles driven: 183 Total miles driven: 255
TRADUCIDO POR ADOLFO PANDURO