Module: BFS - 广度行走


Problem

4 /6


小路

Theory Click to read/hide

要恢复最短路径,创建一个“祖先”数组\(p[]\) ,其中,对于每个顶点,存储我们命中该顶点的顶点数。

Problem

在无向图中,您需要找到两个顶点之间的最小路径。
 
输入: 
- 第一行包含数字 N - 图中的顶点数 (\(1<=N<=100\) );
- 下一行设置邻接矩阵(0表示无边,1 - 有边);
- 最后一行包含两个顶点的数量 - 初始和最终。
 
输出: 首先打印 L - 路径的长度(要通过的边数)。 然后打印< code>L+1 数字 - 沿此路径排列的顶点。如果路径不存在,打印一个数字 -1.

例子
<头> <正文>
# 输入 输出
1
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
3
3 2 1 5