hint

먼저 모든 두 쌍의 도시들에 대해서 횡단경로를 설치한 다음 모든 도시에 대해서 가장 최장거리가 짧은 쌍을 찾는다.

횡단경로가 결정된 상태에서 어떠한 도시에서 최장경로를 찾는 방법은 각 도시간의 거리와 각 도시의 최장거리를 미리 저장함으로써 상수 시간 안에 해결되므로 전체 시간 복잡도는 O(n^3) 이다