Problem
加重有向グラフが与えられます。負の重みのサイクルが含まれているかどうかを判断する必要があります。グラフのすべての頂点が最初の頂点から到達可能であることが保証されています。
入力:
入力ファイルの最初の行には、 n と m —の 2 つの自然数が含まれています。それぞれグラフの頂点と辺の数 ( n ≤ 1 111, m ≤ 11 111).
次の m 行には、エッジの説明が 1 行に 1 つずつ含まれています。エッジ番号 i は、bi、ei、wi の 3 つの数値で表されます。それぞれ肋骨の端の数とその重さ (1 ≤ bi, ei ≤ n, −100 ≤ wi ≤ 100 000) .グラフには複数のエッジとループを含めることができることに注意してください。
出力:
グラフに負の重みのサイクルが含まれている場合、出力ファイルの最初の行には yes が含まれ、no が含まれている必要があります。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| はい |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| いいえ |