Longueur du trajet
Problem
Dans un graphe non orienté, vous voulez trouver la longueur du chemin le plus court entre deux sommets.
Saisie :
- la première ligne de l'entrée contient le nombre N - le nombre de sommets dans le graphe (\(1<=N<=100\));< br />
- ensuite, la matrice d'adjacence est écrite à partir d'une nouvelle ligne (0 indique l'absence d'arête, 1 - la présence d'une arête) ;
- la dernière ligne contient les numéros de deux sommets - début et fin.
Sortie : Imprime la longueur du chemin le plus court. Si le chemin n'existe pas, imprimez un seul numéro -1.
Exemples
| # |
Entrée |
Sortie |
| 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 |