最短距离II

题目内容

题目描述

给出一个无向图,求在该图中任意两点之间,最少经过几条边可以到达

图中可能存在重边(即连接同一对顶点的两条及以上的边)和自环(即连接某个点和它自身的边)

输入描述

输入的第一行为2个正整数n,m。分别表示给出的图的顶点数和边数。(1 <= n <= 200, 1 <= m <= n*(n-1)/2 )

接下来m行,每行两个正整数x,y。表示一条边的两个顶点编号。(顶点编号从1到n)

输出描述

输出包含n行,每行包含n个数,第i行第j个数表示从顶点i到顶点j,最少经过几条边可以到达,如果不可达,则输出-1

样例输入

5 3 1 2 2 3 4 5

样例输出

0 1 2 -1 -1 1 0 1 -1 -1 2 1 0 -1 -1 -1 -1 -1 0 1 -1 -1 -1 1 0

提示

分别以每个点为起点,调用一次bfs即可
提交评测
请登录后再操作

题目描述

最短距离II
1605
0
40
9
23%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在