Ciclo negativo. ciclo negativo
Problem
Um grafo direcionado ponderado é dado. É necessário determinar se contém um ciclo de peso negativo. É garantido que todos os vértices do grafo são alcançáveis a partir do primeiro.
Entrada:
A primeira linha do arquivo de entrada contém dois números naturais n e m — o número de vértices e arestas do grafo respectivamente ( n ≤ 1 111, m ≤ 11 111).
As próximas m linhas contêm a descrição das arestas, uma por linha. O número de borda i é descrito por três números bi, ei e wi — os números das pontas da nervura e seu peso, respectivamente (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . Observe que o gráfico pode ter várias arestas e loops.
Saída:
A primeira linha do arquivo de saída deve conter sim se o gráfico contiver um ciclo de peso negativo e não — caso contrário.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| sim |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| não |