Problem
Un graphe acyclique pondéré orienté est donné. Il est nécessaire d'y trouver le chemin le plus court
du sommet s au sommet t.
Saisie :
La première ligne du fichier d'entrée contient quatre entiers n, m, s et t - le nombre de sommets, d'arêtes du graphe, les sommets initial et final, respectivement (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
Les m lignes suivantes contiennent les descriptions des arêtes, une par ligne.
L'arête numéro i est décrite par trois entiers b
i, e
i et w
i - le début, la fin et la longueur de l'arête, respectivement ( 1 <= b
i, e
i <= n;|w
i| <= 1000).
Le graphique ne contient pas de cycles et de boucles.
Sortie :
La première ligne du fichier de sortie doit contenir un seul entier - la longueur du chemin le plus court de s à t.
S'il n'y a pas de chemin de s à t, écrivez "Inaccessible".
Exemples :
| Entrée |
Sortie |
2 1 1 2
1 2 -10
| -10 |
2 1 2 1
1 2 -10
| Injoignable |