Module: algoritmo de floyd


Problem

6 /10


ciclo negativo

Theory Click to read/hide

Dado que el algoritmo de Floyd relaja secuencialmente las distancias entre todos los pares de vértices (i, j), incluidos aquellos con i=j, y la distancia inicial entre un par de vértices (i, i) es igual a cero, entonces la relajación solo puede ocurrir si el vértice k tal que d[i][k]+d[k][i]<0, lo que equivale a tener un ciclo negativo a través del vértice i

Problem

Dada una gráfica dirigida. Determine si tiene un ciclo de peso negativo.

Entrada
La primera línea contiene el número N (1 <= N <= 100) – el número de vértices del gráfico. Las siguientes N líneas contienen N números cada una – matriz de adyacencia de grafos. Los pesos de borde tienen un módulo inferior a 100000. Si no hay borde, el valor correspondiente es 100000.
 
Salida
En la primera línea escriba "SÍ" si el ciclo existe, o "NO" en caso contrario. 

Ejemplos

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!

# Entrada Salida
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 SI