Problem
Um gráfico acíclico ponderado direcionado é dado. É necessário encontrar o caminho mais curto nele
do vértice s ao vértice t.
Entrada:
A primeira linha do arquivo de entrada contém quatro inteiros n, m, s e t - o número de vértices, arestas do gráfico, os vértices inicial e final, respectivamente (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
As próximas m linhas contêm as descrições das arestas, uma por linha.
O número da aresta i é descrito por três inteiros b
i, e
i e w
i - o início, o fim e o comprimento da aresta, respectivamente ( 1 <= b
i, e
i <= n;|w
i| <= 1000).
O gráfico não contém ciclos e loops.
Saída:
A primeira linha do arquivo de saída deve conter um único inteiro - o comprimento do caminho mais curto de s a t.
Se não houver caminho de s para t, imprima "Inalcançável".
Exemplos:
| Entrada |
Saída |
2 1 1 2
1 2 -10
| -10 |
2 1 2 1
1 2 -10
| Inacessível |