BFS cơ bản
View as PDF
Submit solution
Points:
300.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho một đồ thị vô hướng gồm ~N~ đỉnh đánh số từ 1 tới ~N~ và ~M~ cạnh. Độ dài của mỗi cạnh có giá trị là 1. Một đồ thị sẽ có 1 nút trung tâm ~S~.
Yêu cầu: với mỗi đỉnh có thể tới được từ đỉnh ~S~, tính khoảng cách ngắn nhất từ đỉnh đó tới ~S~ và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần. Lưu ý: nếu 2 đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.
Input
- Dòng đầu gồm 3 số nguyên ~N, M, S~ (~N \leq 100000, M \leq 100000, 1 \leq S \leq N~)
- M dòng sau mỗi dòng gồm 2 số thể hiện 2 đầu của một cạnh.
Output
- In ra số dòng tương ứng với số đỉnh có thể tới được từ S theo thứ tự khoảng cách ngắn nhất tăng dần.
- Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới S.
Sample input
7 6 1
1 2
2 3
3 4
4 5
5 6
1 3
Sample output
1 0
2 1
3 1
4 2
5 3
6 4
Comments
iloveamelia><