5262 : A63 - 최단 경로 1
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 개의 정점과 $M$ 개의 간선으로 이루어진 무향 그래프가 주어집니다. 각 정점에는 1부터 $N$ 까지 번호가 붙어 있으며, $i$ 번째 간선은 정점 $A_i$ 와 $B_i$ 를 연결합니다.
1 이상 $N$ 이하의 모든 정수 $k$ 에 대해 다음 물음에 답하세요.
[제약 조건]
• $2 \le N \le 10^5$
• $1 \le M \le \min(10^5, \frac{N(N-1)}{2})$
• $1 \le U_i, V_i \le N$
• 입력되는 모든 값은 정수입니다.
1 이상 $N$ 이하의 모든 정수 $k$ 에 대해 다음 물음에 답하세요.
정점 1에서 정점 $k$ 까지 간선을 따라 이동할 때, 거쳐야 하는 간선의 최소 개수를 출력하세요. 이동이 불가능한 경우 -1을 출력하세요.
[제약 조건]
• $2 \le N \le 10^5$
• $1 \le M \le \min(10^5, \frac{N(N-1)}{2})$
• $1 \le U_i, V_i \le N$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$ 이 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보가 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보가 주어집니다.
출력 설명
각 정점 1부터 $N$ 까지의 최단 거리를 한 줄에 하나씩 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
1 3
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
2
1