Module: BFS - Breadth Walk


Problem

4 /6


Laluan

Theory Click to read/hide

Untuk memulihkan laluan terpendek, buat tatasusunan "nenek moyang" \(p[]\) , di mana, untuk setiap bucu, menyimpan nombor bucu yang kita gunakan untuk mencapai bucu ini.

Problem

Dalam graf tidak terarah, anda perlu mencari laluan minimum antara dua bucu. 
 
Input: 
- baris pertama mengandungi nombor N - bilangan bucu dalam graf (\(1<=N<=100\) );
- baris seterusnya menetapkan matriks bersebelahan (0 bermaksud tiada tepi, 1 - tepi);
- baris terakhir mengandungi nombor dua bucu - awal dan akhir.
 
Output: cetak dahulu L - panjang laluan (bilangan tepi untuk lalui). Kemudian cetak Nombor < code>L+1 - bucu mengikut urutan di sepanjang laluan ini. Jika laluan tidak wujud, cetak satu nombor -1.

Contoh

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!

# Input Output
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