Problem

6 /10


cycle négatif

Theory Click to read/hide

Étant donné que l'algorithme de Floyd relâche séquentiellement les distances entre toutes les paires de sommets (i, j), y compris celles avec i = j, et que la distance initiale entre une paire de sommets (i, i) est égale à zéro, alors la relaxation ne peut se produire que si sommet k tel que d[i][k]+d[k][i]<0, ce qui équivaut à avoir un cycle négatif passant par le sommet i

Problem

Étant donné un graphe orienté. Déterminez s'il a une boucle de poids négative.

Entrée
La première ligne contient le nombre N (1 <= N <= 100) – le nombre de sommets du graphe. Les N lignes suivantes contiennent N nombres chacune – matrice d'adjacence de graphe. Les poids des arêtes sont modulo inférieurs à 100 000. S'il n'y a pas d'arête, la valeur correspondante est 100 000.
 
Sortie
Sur la première ligne écrivez "OUI" si le cycle existe, ou "NON" sinon. 

Exemples
3
100000 100000 -51
100  ; 100000 100000
100000 -50  100000
# Entrée Sortie
1 OUI

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!