Negcycle. Negativer Zyklus
Problem
Ein gewichtetes, orientiertes Diagramm ist gegeben. Es muss festgestellt werden, ob es einen negativen Gewichtszyklus enthält. Es ist garantiert, dass alle Eckpunkte des Graphen von der ersten aus erreichbar sind.
Eingabe:
Die erste Zeile der Eingabedatei enthält zwei natürliche Zahlen n und m — die Anzahl der Scheitelpunkte und Kanten des Graphen ( n ≤ 1 111, m ≤ 11 111).
Die folgenden m Zeilen enthalten eine Beschreibung der Kanten nacheinander pro Zeile. Die Rippennummer i wird durch die drei Zahlen bi, ei und wi, die Endnummern der Rippen und ihr Gewicht jeweils beschrieben (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Beachten Sie, dass es ein Vielfaches von Kanten und Schleifen in der Grafik geben kann.
Ausgabe:
Die erste Zeile der Ausgabedatei sollte yes enthalten, wenn das Diagramm eine Schleife mit negativem Gewicht enthält, andernfalls no .
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
4 4
2 1 -4
1 2 1
3 4 2
2 3 3 |
yes |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2 |
no |