Module: BFS - Breadth Walk


Problem

4 /6


Path

Theory Click to read/hide

To restore shortest paths, create an array of "ancestors" \(p[]\), in which, for each vertex, store the number of the vertex by which we hit this vertex.

Problem

In an undirected graph, you need to find the minimum path between two vertices. 
 
Input: 
- the first line contains the number N - the number of vertices in the graph (\(1<=N<=100\));
- the next lines set the adjacency matrix (0 means no edge, 1 - edge);
- the last line contains numbers of two vertices - initial and final.
 
Output: print first L - the length of the path (number of edges to pass). Then print < code>L+1 number - vertices in order along this path. If the path does not exist, print a single number -1.

Examples
# Input Output
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

time 1000 ms
memory 32 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!