5363 : B64 - 최단 경로와 복원
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 수 $N$, 간선 수 $M$인 가중치 없는 무방향 그래프가 주어집니다. 정점 $1$에서 정점 $N$까지의 구체적인 최단 경로를 하나 출력하십시오. (다익스트라 알고리즘 사용 권장)
[제약 조건]
• $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$ 은 연결되어 있습니다.
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $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$ 은 연결되어 있습니다.
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$이 주어집니다.
이후 $M$개 줄에 각 간선의 정보 $A_i, B_i, C_i$가 주어집니다.
이후 $M$개 줄에 각 간선의 정보 $A_i, B_i, C_i$가 주어집니다.
출력 설명
최단 경로상의 정점 번호들을 순서대로 출력하십시오.
입력 예시
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
복사되었습니다!
복사되었습니다!
1 2 5 6