그래프 복원
시간 제한2초메모리 제한128 MB
연결된 가중 그래프의 모든 정점 쌍 최단거리가 주어질 때, 이를 정확히 만족하는 M개의 간선을 가진 그래프를 구성하거나 불가능함을 판별하는 문제입니다.
문제
정점이 N개이고 간선이 M개인 연결된 가중 무향 그래프가 있다. 정점은 1부터 N까지 번호가 붙어 있다.
그래프의 실제 간선 정보는 알려져 있지 않지만, 서로 다른 모든 두 정점 사이의 최단 거리는 주어진다. 주어진 최단 거리 정보와 일치하는 그래프를 하나 구성하라.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1,000)
다음 N-1개의 줄에는 최단 거리 정보가 주어진다. 그중 i번째 줄에는 정점 i에서 정점 i+1, i+2, ..., N까지의 최단 거리가 이 순서대로 공백으로 구분되어 주어진다.
모든 최단 거리는 500 이하의 자연수이다.
출력
주어진 최단 거리와 정확히 일치하는 그래프를 구성할 수 없으면 첫째 줄에 0을 출력한다.
구성할 수 있으면 첫째 줄에 1을 출력하고, 이어서 M개의 줄에 간선을 하나씩 출력한다. 각 줄은 a b c 형식이며, 정점 a와 b를 잇는 가중치 c인 간선을 뜻한다. a와 b는 서로 달라야 하고, c는 500 이하의 자연수여야 한다.