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 NM 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 (N100000,M100000,1SN)
  • 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

Copy
7 6 1
1 2
2 3
3 4
4 5
5 6
1 3

Sample output

Copy
1 0
2 1
3 1
4 2
5 3
6 4

Comments

Please read the guidelines before commenting.