Otra Fiesta Vacuna


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Una vaca de cada una de N granjas (1 \le N \le 1000) convenientemente numeradas 1..N van a ir a una gran fiesta vacuna que tendrá lugar en la granja X (1 \le X \le N). Un total de M (1 \le M \le 100,000) carreteras unidireccionlaes (de un sentido) conectan pares de granjas; la carretera i requiere T_i (1 \le Ti \le 100) 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 N, M y X.

Líneas 2..M+1: La línea i+1 describe la carretera i con tres enteros separados por espacios: A_i, B_i, y T_i. La carretera descrita va de la granja A_i a la granja B_i, requiriendo T_i 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

There are no comments at the moment.