Module: BFS - Caminata de amplitud


Problem

4 /6


Camino

Theory Click to read/hide

Para restaurar las rutas más cortas, cree una matriz de "ancestros" \(p[]\) , en el que, para cada vértice, almacena el número del vértice por el que golpeamos este vértice.

Problem

En un gráfico no dirigido, debe encontrar la ruta mínima entre dos vértices. 
 
Entrada: 
- la primera línea contiene el número N - el número de vértices en el gráfico (\(1<=N<=100\) );
- las líneas siguientes establecen la matriz de adyacencia (0 significa sin borde, 1 - borde);
- la última línea contiene números de dos vértices - inicial y final.
 
Salida: imprime primero L - la longitud del camino (número de aristas por pasar). Luego imprime < code>L+1 número - vértices en orden a lo largo de esta ruta. Si la ruta no existe, imprima un solo número -1.

Ejemplos

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!

# Entrada Salida
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