Module: BFS - Caminhada em Largura


Problem

4 /6


Caminho

Theory Click to read/hide

Para restaurar os caminhos mais curtos, crie uma matriz de "ancestrais" \(p[]\) , em que, para cada vértice, armazenamos o número do vértice pelo qual atingimos esse vértice.

Problem

Em um gráfico não direcionado, você precisa encontrar o caminho mínimo entre dois vértices. 
 
Entrada: 
- a primeira linha contém o número N - o número de vértices no grafo (\(1<=N<=100\) );
- as próximas linhas definem a matriz de adjacência (0 significa sem borda, 1 - borda);
- a última linha contém números de dois vértices - inicial e final.
 
Saída: imprima primeiro L - o comprimento do caminho (número de arestas para passar). Em seguida, imprima < code>L+1 número - vértices em ordem ao longo deste caminho. Se o caminho não existir, imprima um único número -1.

Exemplos
# Entrada Saída
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!