https://www.acmicpc.net/problem/12880


0번부터 N-1번까지 번호가 있는 정점들로 구성된 방향성 가중치 그래프가 있다. 서로 다른 모든 정점 사이에 방향성 가중치 간선이 있다. 따라서 간선은 총 N*(N-1)개가 존재한다. 이 중 몇 개의 간선을 선택하여, 임의의 두 정점을 선택하였을 때에 항상 경로가 있도록 선택해야 한다. 예를 들어 N=3일 때에 가능한 간선 선택으로, 0 ⇒ 1, 1 ⇒ 0, 0 ⇒ 2, 2 ⇒ 0이 있고, 또는 0 ⇒ 1, 1 ⇒ 2, 2 ⇒ 0도 가능하다. 선분 선택을 마치고 새로이 생성되는 그래프의 가장 큰 가중치 값과 가장 작은 가중치 값 차이를 최소화하고 싶다. 가능한 선택에서의 가중치 최대 최소 차이의 최솟값을 구하시오.