6194 : 다익스트라 경로 복원
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
출발 노드 S에서 도착 노드 E까지의 최단 경로의 길이와 경로를 함께 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N, 간선의 개수 E (1 ≤ N, E ≤ 100,000), 출발 노드 S와 도착 노드 E가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다.
출력 설명
첫째 줄에 S에서 E까지의 최단 거리를 출력하고, 둘째 줄에 경로에 포함된 노드의 번호를 순서대로 공백으로 구분해 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 6 1 5
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6
1 2 3 5