Module: フロイドのアルゴリズム


Problem

6 /10


負のサイクル

Theory Click to read/hide

Floyd アルゴリズムは、i=j の頂点を含むすべての頂点のペア (i, j) 間の距離を順次緩和し、頂点のペア (i, i) 間の初期距離はゼロに等しいため、緩和はのみ発生します。頂点 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
 はい