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
 是