Module: BFS - Umgehung in der Breite


Problem

4 /6


Der Weg

Theory Click to read/hide

Um die kürzesten Möglichkeiten wiederherzustellen, müssen wir eine Reihe von Raubtieren einrichten.- Ja.in denen wir für jeden Top die Anzahl der Top haben wir in dieser Spitze.

Problem

In einem nicht ausgerichteten Graphen ist es erforderlich, den minimalen Pfad zwischen zwei Scheitelpunkten zu finden. 
 
Eingabe: 
- die Zahl N ist in der ersten Zeile geschrieben - die Anzahl der Scheitelpunkte im Graphen(\(1<=N<=100\));
- in den folgenden Zeilen ist eine Adjazenzmatrix angegeben (0 bedeutet, dass keine Kante vorhanden ist, 1 bedeutet, dass eine Kante vorhanden ist);
- in der letzten Zeile werden die Zahlen der beiden Eckpunkte - der Anfangs- und der Endpunkte - aufgezeichnet.
 
Ausgabe: Geben Sie zuerst L aus - die Länge des Pfads (die Anzahl der Kanten, die durchlaufen werden muss). Geben Sie dann L+1 die Zahl - Scheitelpunkte in der Reihenfolge aus, in der Sie entlang dieses Pfads folgen. 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
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!