Problem
Étant donné un graphique pondéré orienté avec des bords négatifs (pas de cycles négatifs).
Étant donné un sommet de début et de fin, définissez la distance minimale entre eux.
Saisie :
Étant donné 4 nombres n, m, s, f - nombre de sommets, nombre d'arêtes, sommet de début et de fin (à partir de 1), respectivement.
Les m lignes suivantes contiennent chacune 3 nombres - sommet 1, sommet 2 et le prix de la transition entre les sommets.
Sortie :
Il est nécessaire d'afficher un numéro - la réponse à la tâche. S'il n'y a pas de réponse, sortez Inf.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4 2 1 4
1 2 100500
2 3 100500
Inf |