6197 : 플로이드-워셜 경로
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
모든 노드 쌍 (i, j)에 대해 최단 경로의 길이와 경로 상의 노드 개수 및 노드 목록을 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 200)과 간선의 개수 E (1 ≤ E ≤ 10,000)가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다.
둘째 줄부터 E개의 줄에 간선 정보 u, v, w가 주어집니다.
출력 설명
모든 노드 쌍 (i, j)에 대해 (단 i=j이거나 도달 불가능하면 0 한 줄 출력) 최단 거리, 노드 개수, 경로 노드들을 순서대로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3
1 2 5
2 3 2
1 3 10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
5 2 1 2
7 3 1 2 3
0
0
2 2 2 3
0
0
0