Module: BFS - Đi bộ theo chiều rộng


Problem

4 /6


Con đường

Theory Click to read/hide

Để khôi phục các đường đi ngắn nhất, hãy tạo một mảng "tổ tiên" \(p[]\) , trong đó, với mỗi đỉnh, lưu số của đỉnh mà chúng ta đánh vào đỉnh đó.

Problem

Trong đồ thị vô hướng, bạn cần tìm đường đi nhỏ nhất giữa hai đỉnh. 
 
Đầu vào: 
- dòng đầu tiên chứa số N - số đỉnh của đồ thị (\(1<=N<=100\) );
- các dòng tiếp theo đặt ma trận kề (0 nghĩa là không có cạnh, 1 - cạnh);
- dòng cuối cùng ghi số của hai đỉnh - đỉnh đầu và đỉnh cuối.
 
Đầu ra: in đầu tiên L - độ dài của đường dẫn (số cạnh để đi qua). Sau đó in < code>L+1 số - các đỉnh theo thứ tự dọc theo đường dẫn này. Nếu đường dẫn không tồn tại, hãy in một số duy nhất -1.

Ví dụ
<đầu>

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!

# Đầu vào Đầu ra
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