Module: algoritmo de Floyd


Problem

6 /10


ciclo negativo

Theory Click to read/hide

Como o algoritmo Floyd relaxa sequencialmente as distâncias entre todos os pares de vértices (i, j), incluindo aqueles com i=j, e a distância inicial entre um par de vértices (i, i) é igual a zero, então o relaxamento pode ocorrer apenas se o vértice k tal que d[i][k]+d[k][i]<0, que é equivalente a ter um ciclo negativo através do vértice i

Problem

Dado um grafo direcionado. Determine se ele tem um ciclo de peso negativo.

Entrada
A primeira linha contém o número N (1 <= N <= 100) – o número de vértices do gráfico. As próximas N linhas contêm N números cada – matriz de adjacência do grafo. Pesos da aresta módulo menor que 100.000. Se não houver aresta, o valor correspondente é 100.000.
 
Saída
Na primeira linha imprima "SIM" se o ciclo existir, ou "NÃO" caso contrário. 

Exemplos
# Entrada Saída
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 SIM

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!