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


Problem

9 /10


フロイド - 存在

Theory Click to read/hide

負の重みのサイクルを通過するパスは不可能になります。

Problem

有向加重グラフが表示されます。隣接行列を使用して、頂点の各ペアについて、それらの間に最短経路があるかどうかを判断する必要があります。
 
コメント: 最短経路は、次の 2 つの理由で存在しない可能性があります:
  • パスはありません
  • 任意の重みの小さいパスがあります
     
入力
入力ファイルの最初の行には、単一の数値が含まれています: N (1 <=N <=100) —グラフの頂点の数。次の N 行には、それぞれ N 個の数字が含まれています。グラフの隣接行列 (i 番目の行の j 番目の数値は、頂点 i から頂点 j までのエッジの重みに対応します): 数値 0 はエッジがないことを意味し、その他の数値は —対応する重みのエッジの存在。すべてのモジュロ数は 100 を超えません。
 
出力
N 個の数字を N 行に出力します。 i 行目の j 番目の数字は、頂点 i から頂点 j への最短経路に対応している必要があります。パスがない場合は 0、最短パスがある場合は 1、パスはあるが重みが任意に小さいパスがある場合は 2 になります。

例 <頭> <本体>

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
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0 
1 1 1 0 0 
1 1 1 0 0 
1 1 1 0 0 
0 0 0 2 2 
0 0 0 2 2