Problem
Se proporciona un gráfico acíclico ponderado dirigido. Se requiere encontrar el camino más corto en él
del vértice s al vértice t.
Entrada:
La primera línea del archivo de entrada contiene cuatro enteros n, m, s y t - el número de vértices, bordes del gráfico, los vértices inicial y final, respectivamente (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
Las siguientes m líneas contienen las descripciones de los bordes, una por línea.
El número de arista i se describe mediante tres números enteros b
i, e
i y w
i: el comienzo, el final y la longitud de la arista, respectivamente ( 1 <= b
i, e
i <= n;|w
i| <= 1000).
El gráfico no contiene ciclos ni bucles.
Salida:
La primera línea del archivo de salida debe contener un solo número entero: la longitud de la ruta más corta de s a t.
Si no hay una ruta de s a t, imprima "Inalcanzable".
Ejemplos:
| Entrada |
Salida |
2 1 1 2
1 2 -10
| -10 |
2 1 2 1
1 2 -10
| Inalcanzable |