Problem
Ağırlıklı yönlendirilmiş bir grafik verilmiştir. Negatif ağırlık döngüsü içerip içermediğinin belirlenmesi gerekir. Grafiğin tüm köşelerine ilkinden erişilebilir olması garanti edilir.
Giriş:
Girdi dosyasının ilk satırı iki doğal sayı içerir n ve m — sırasıyla grafiğin köşe ve kenarlarının sayısı ( n ≤ 1 111, m ≤ 11 111).
Sonraki m satır, her satırda bir tane olmak üzere kenarların açıklamasını içerir. Kenar sayısı i, üç sayı bi, ei ve wi ile tanımlanır — kaburganın uçlarının sayısı ve ağırlığı, sırasıyla (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . Grafiğin birden fazla kenarı ve döngüsü olabileceğini unutmayın.
Çıktı:
Grafik bir negatif ağırlık ve hayır döngüsü içeriyorsa, çıktı dosyasının ilk satırı yes ifadesini içermelidir— aksi halde.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| evet |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| hayır |