6180 : 재구성 트리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
모든 노드 쌍 간의 최단 거리가 행렬 D로 주어질 때, 이 최단 거리를 만족하는 원래 트리의 연결 상태(간선 가중치 정보)를 재구성하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 1,000)이 주어집니다.
둘째 줄부터 N개의 줄에 N×N 크기의 최단 거리 행렬 D가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 N×N 크기의 최단 거리 행렬 D가 공백으로 구분되어 주어집니다.
출력 설명
원래 트리의 간선 연결 상태
u v w를 N-1줄에 걸쳐 u 기준 오름차순, u가 같으면 v 기준 오름차순으로 정렬하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
0 5 8
5 0 3
8 3 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 2 5
2 3 3