|
|
4454 - Subway
Timing |
||||
|
|
|
||||
Como la mayoría de las ciudades modernas, Estocolmo cuenta con un bien desarrollado sistema de transporte público. El corazón del transporte público en Estocolmo es el metro. Un mapa de la topología del sistema de metro ilustra las diferentes líneas de metro y la forma en que están conectados, como se ilustra en la Figura 8. Para este problema se debe suponer que un mapa de metro está siempre en forma de árbol, aunque este no es del todo cierto porque de Estocolmo para el ciclo formado por las líneas verdes y azules.
Figura 8: Mapa de metro de Estocolmo
Un mapa
topológico dice muy poco acerca de la geometría de un sistema de metro, como
las distancias (y, por consiguiente, los tiempos de viaje) entre las diferentes
estaciones de metro. Por ejemplo, en la mayoría de los estudiantes en Estocolmo
saber, la distancia entre `` Tekniska Högskolan "(The Royal Institute of
Technology) y `` Universitetet (Universidad de Estocolmo) es bastante grande,
aunque no hay indicios de esto en el mapa.
Usted debe escribir un programa que puede aumentar un mapa topológico de anotar
el tiempo necesario para los viajes entre cada par de estaciones de metro
adyacente. Afortunadamente, los tiempos de viaje son conocidos, por lo que no
tiene que medir el tiempo a ti mismo. No obstante, la duración del viaje se da
en segundos, mientras que los tiempos deben ser escritos en el mapa como
integrante de las estimaciones del número de minutos.
Una forma natural de la estimación puede ser a veces simplemente la ronda de
todos los tiempos de viaje al minuto más cercano. Sin embargo, esto puede
causar enormes errores acumulativos. Por ejemplo, en el mapa de Estocolmo, este
método de estimación podría resultar en un error tan grande como 15 minutos en
el total de tiempo de viaje entre algunos pares de estaciones. Para
contrarrestar esto, el programa puede optar por ronda algunos de los tiempos de
viaje y otros gastos de viaje redondo veces hacia abajo. El redondeo debe
hacerse de tal manera que el mayor error acumulado entre cualquier par de
estaciones es mínimo.
Input
La
entrada consiste de varios casos de prueba. Cada caso de prueba se inicia con
un número entero N (1 N 100), que es el número de estaciones de metro. La N estaciones se identifican mediante los números enteros de 1 a N. Cada uno de los próximos N - 1 contiene tres líneas de enteros a, b, t (1 a, b N, y 1 t 300), lo que indica que las estaciones A y B son adyacentes y que no tiene segundos
para viajar entre ellos. Para simplificar, pasar por alto la vez que un tren
pasa de pie aún en una estación.
La última prueba es seguida por el número entero de cero en una línea por sí
mismo.
Output
Para cada caso de prueba, imprimir el número del caso (a partir de 1) entonces el mayor error de redondeo en segundos de tiempo de viaje entre cualquier par de estaciones cuando los tiempos de pares adyacentes de las estaciones se han redondeado óptimos. Seguir el formato de la muestra de salida.
Sample Input
2
1 2 110
4
1 2 40
2 3 40
3 4 40
4
1 2 90
1 3 90
1 4 90
0
Sample Output
Case 1: 10
Case 2: 40
Case 3: 60
Stockholm 2008-2009
TRADUCIDO POR: ALCANTARA TORRES PEDRO