Négcycle. cycle négatif
Problem
Un graphe orienté pondéré est donné. Il est nécessaire de déterminer s'il contient un cycle de poids négatif. Il est garanti que tous les sommets du graphe sont accessibles depuis le premier.
Entrée :
La première ligne du fichier d'entrée contient deux nombres naturels n et m — le nombre de sommets et d'arêtes du graphe respectivement ( n ≤ 1 111, m ≤ 11 111).
Les m lignes suivantes contiennent la description des arêtes, une par ligne. L'arête numéro i est décrite par trois nombres bi, ei et wi — les numéros des extrémités de la côte et son poids, respectivement (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . Notez que le graphique peut avoir plusieurs arêtes et boucles.
Sortie :
La première ligne du fichier de sortie doit contenir oui si le graphique contient un cycle de poids négatif et non — sinon.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| oui |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| non |