6111 : 다중 출발 BFS
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 N개와 간선 M개인 무방향 그래프에서 여러 개의 시작 노드 번호 K개가 동시에 주어집니다.
모든 노드에 대해, 자신과 가장 가까운 시작 노드로부터의 최단 거리를 구하는 프로그램을 작성하십시오.
모든 노드에 대해, 자신과 가장 가까운 시작 노드로부터의 최단 거리를 구하는 프로그램을 작성하십시오.
입력 설명
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 1,000)과 간선의 개수 M (0 ≤ M ≤ 10,000)이 주어집니다.
둘째 줄에 시작 노드의 개수 K (1 ≤ K ≤ N)가 주어집니다.
셋째 줄에 K개의 시작 노드 번호가 공백으로 구분되어 주어집니다.
넷째 줄부터 M개의 줄에 간선 u v가 주어집니다.
둘째 줄에 시작 노드의 개수 K (1 ≤ K ≤ N)가 주어집니다.
셋째 줄에 K개의 시작 노드 번호가 공백으로 구분되어 주어집니다.
넷째 줄부터 M개의 줄에 간선 u v가 주어집니다.
출력 설명
1번 노드부터 N번 노드까지 순서대로, 가장 가까운 시작지점으로부터의 거리를 공백으로 구분하여 한 줄에 출력합니다. 시작지점 자체의 거리는 0이며, 시작지점들로부터 도달 불가능한 노드는 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
2
1 4
1 2
2 3
3 4
4 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 1 1 0 1도움
다중 소스(Multi-source) BFS 기법을 활용합니다. 탐색 초기에 모든 시작 정점을 일시에 큐에 밀어 넣고 동시에 탐색을 시작하면, 자연스럽게 각 노드는 가장 먼저 자신을 찾아온 소스로부터의 최소 거리가 결정됩니다.