Negciclo. ciclo negativo
Problem
Viene fornito un grafico orientato pesato. È necessario determinare se contiene un ciclo di peso negativo. È garantito che tutti i vertici del grafo siano raggiungibili dal primo.
Input:
La prima riga del file di input contiene due numeri naturali n e m — rispettivamente il numero di vertici e spigoli del grafico ( n ≤ 1 111, m ≤ 11 111).
Le m righe successive contengono la descrizione dei bordi, uno per riga. Il numero di bordo i è descritto da tre numeri bi, ei e wi — i numeri delle estremità della costola e il suo peso, rispettivamente (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . Tieni presente che il grafico può avere più spigoli e loop.
Uscita:
La prima riga del file di output deve contenere yes se il grafico contiene un ciclo di peso negativo e no — altrimenti.
Esempi
| # |
Input |
Uscita |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| sì |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| no |