Module: L'algoritmo di Floyd


Problem

6 /10


ciclo negativo

Theory Click to read/hide

Poiché l'algoritmo di Floyd rilassa sequenzialmente le distanze tra tutte le coppie di vertici (i, j), comprese quelle con i=j, e la distanza iniziale tra una coppia di vertici (i, i) è uguale a zero, allora il rilassamento può avvenire solo se vertice k tale che d[i][k]+d[k][i]<0, che equivale ad avere un ciclo negativo attraverso il vertice i

Problem

Dato un grafico orientato. Determina se ha un ciclo di peso negativo.

Input
La prima riga contiene il numero N (1 <= N <= 100) – il numero di vertici del grafo. Le successive N righe contengono N numeri ciascuna – matrice di adiacenza del grafo. Pesi degli spigoli modulo inferiori a 100000. Se non ci sono spigoli, il valore corrispondente è 100000.
 
Uscita
Sulla prima riga stampa "SI" se il ciclo esiste, oppure "NO" in caso contrario. 

Esempi
# Input Uscita
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 SÌ

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!