Module: BFS - Camminata in larghezza


Problem

4 /6


Sentiero

Theory Click to read/hide

Per ripristinare i percorsi più brevi, crea un array di "antenati" \(p[]\) , in cui, per ogni vertice, memorizza il numero del vertice con cui abbiamo colpito questo vertice.

Problem

In un grafo non orientato, devi trovare il percorso minimo tra due vertici. 
 
Inserimento: 
- la prima riga contiene il numero N - il numero di vertici nel grafico (\(1<=N<=100\) );
- le righe successive impostano la matrice di adiacenza (0 significa nessun bordo, 1 - bordo);
- l'ultima riga contiene i numeri di due vertici - iniziale e finale.
 
Output: stampa prima L - la lunghezza del percorso (numero di spigoli da passare). Quindi stampa < code>L+1 numero - vertici in ordine lungo questo percorso. Se il percorso non esiste, stampa un singolo numero -1.

Esempi
# Input Uscita
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!