Module: 弗洛伊德算法


Problem

9 /10


弗洛伊德 - 存在

Theory Click to read/hide

通过负重循环的路径变得不可能。

Problem

给你一个有向加权图。使用它的邻接矩阵，您需要确定每对顶点之间是否存在最短路径。
 
评论：最短路径可能不存在有两个原因：
  • 没有路径
  • 有任意小权重的路径
     
输入
输入文件的第一行包含一个数字：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