Otra Fiesta Vacuna
Una vaca de cada una de granjas convenientemente numeradas van a ir a una gran fiesta vacuna que tendrá lugar en la granja . Un total de carreteras unidireccionlaes (de un sentido) conectan pares de granjas; la carretera requiere unidades de tiempo para recorrerse.
Cada vaca debe caminar a la fiesta, y luego cuando se acabe la fiesta, volver a su granja. Cada vaca es floja y por lo tanto elige una ruta óptima con el tiempo más corto. La ruta de regreso de una vaca podría ser diferente de su ruta original debido a que las carreteras son de un sentido.
De todas las vacas, ¿cuál es la cantidad más grande de tiempo que una vaca debe gastar caminando a la fiesta y devolviéndose?
Entrada
Línea 1: Tres enteros separados por espacios, respectivamente , y .
Líneas : La línea describe la carretera con tres enteros separados por espacios: , , y . La carretera descrita va de la granja a la granja , requiriendo unidades para recorrerse
Salida
Línea 1: Un entero: La máxima cantidad de tiempo que cualquier vaca debe caminar.
Ejemplo de Entrada
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Ejemplo de Salida
10
Detalles de la Entrada
Cuatro vacas, ocho carreteras: la fiesta es en la granja 2.
Detalles de la Salida
La vaca 4 va directamente a la fiesta (3 unidades) y se devuelve via las granjas 1 y 3 (7 unidades), para un total de 10 unidades de tiempo.
Comments