5263 : A64 - 최단 경로 2
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
가중치 무향 그래프에 대한 최단 경로 문제를 해결하세요.
구체적으로는 다음과 같은 그래프가 주어질 때, 정점 1에서 각 정점까지의 최단 경로 길이를 구하세요.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le M \le \min(100000,N(N-1)/2)$
• $1 \le A_i \lt B_i \le N\ (1\le i\le M)$
• $1 \le C_i \le 10000\ (1\le i\le M)$
• $i \neq j \implies (A_i,B_i) \neq (A_j,B_j)$
• 입력되는 모든 값은 정수입니다.
구체적으로는 다음과 같은 그래프가 주어질 때, 정점 1에서 각 정점까지의 최단 경로 길이를 구하세요.
- 정점 수는 $N$ , 간선 수는 $M$ 이다.
- $i$ 번째 간선은 정점 $A_i$ 와 정점 $B_i$ 를 연결하며 길이는 $C_i$ 이다.
[제약 조건]
• $2 \le N \le 100000$
• $1 \le M \le \min(100000,N(N-1)/2)$
• $1 \le A_i \lt B_i \le N\ (1\le i\le M)$
• $1 \le C_i \le 10000\ (1\le i\le M)$
• $i \neq j \implies (A_i,B_i) \neq (A_j,B_j)$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$ 이 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보 $A_i, B_i, C_i$ 가 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보 $A_i, B_i, C_i$ 가 주어집니다.
출력 설명
정점 1부터 $N$ 까지의 최단 경로 길이를 한 줄에 하나씩 출력하세요. 도달할 수 없는 경우 -1을 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 7
1 2 15
1 4 20
2 3 65
2 5 4
3 6 50
4 5 30
5 6 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
15
77
20
19
27