Module: 플로이드 알고리즘


Problem

6 /10


네거티브 사이클

Theory Click to read/hide

Floyd 알고리즘은 i=j인 정점을 포함하여 모든 정점 쌍(i, j) 사이의 거리를 순차적으로 완화하고 정점 쌍(i, i) 사이의 초기 거리가 0이므로 완화는 오직 한 쌍의 정점만 발생할 수 있습니다. 정점 k가 d[i][k]+d[k][i]<0인 경우, 이는 정점 i를 통해 음의 순환을 갖는 것과 같습니다.

Problem

유방향 그래프가 주어집니다. 음의 가중치 주기가 있는지 확인합니다.
<사업부>
입력
첫 번째 줄에는 숫자 N이 포함됩니다(1 <= N <= 100) – 그래프 정점의 수. 다음 N 줄에는 각각 N개의 숫자가 포함됩니다. 그래프 인접 행렬. 100000보다 작은 에지 가중치 모듈로. 에지가 없으면 해당 값은 100000입니다.
 
출력
주기가 존재하면 첫 번째 줄에 "YES"를 인쇄하고 그렇지 않으면 "NO"를 인쇄하십시오. 

예 <헤드> <일># <몸>

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!

입력 출력
1 <사업부>3
100000 100000 -51
100  100000 100000
100000 -50  100000
 예