Module: BFS - Marche de la largeur


Problem

4 /6


Chemin

Theory Click to read/hide

Pour restaurer les chemins les plus courts, créez un tableau d'"ancêtres" \(p[]\) , dans lequel, pour chaque sommet, stocke le numéro du sommet par lequel nous atteignons ce sommet.

Problem

Dans un graphe non orienté, vous devez trouver le chemin minimum entre deux sommets. 
 
Entrée : 
- la première ligne contient le nombre N - le nombre de sommets dans le graphe (\(1<=N<=100\) );
- les lignes suivantes définissent la matrice d'adjacence (0 signifie pas de bord, 1 - bord) ;
- la dernière ligne contient les nombres de deux sommets - initial et final.
 
Sortie : imprimer d'abord L - la longueur du chemin (nombre d'arêtes à passer). Puis imprimer < code>L+1 nombre - sommets dans l'ordre le long de ce chemin. Si le chemin n'existe pas, imprimez un seul numéro -1.

Exemples
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
# Entrée Sortie
1 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!