Weglänge
Problem
In einem nicht ausgerichteten Diagramm ist es erforderlich, die Länge des kürzesten Pfads zwischen zwei Stützpunkten zu finden.
Eingabe:
- die Zahl N ist in der ersten Zeile der Eingabe geschrieben - die Anzahl der Scheitelpunkte im Diagramm (\(1<=N<=100\));
- als nächstes wird eine Adjazenzmatrix aus einer neuen Zeile geschrieben (0 bedeutet, dass keine Kante vorhanden ist, 1 bedeutet, dass eine Kante vorhanden ist);
- Die letzte Zeile enthält die Zahlen der beiden Scheitelpunkte, den Anfangs- und den Endpunkt.
Ausgabe: Geben Sie die Länge des kürzesten Pfads aus. Wenn kein Pfad vorhanden ist, geben Sie eine Zahl -1 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 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 |