어떤 계획도시 하나를 떠올려보자. 이 도시의 중심에는 거대한 원형 교차로가 하나 존재한다.
교차로에서 바깥으로 벗어나가는 도로들은 각각의 작은 마을와 연결되어 있다.

원형 교차로는 놀랍도록 정교하게 지어져 있어서 각 교차로마다 일정한 거리를 가지고 있다. 이 거리를 1이라고 하자.
추가적으로 작은 마을을 연결하는 모든 도로의 상대 거리를 알 수 있다면 우리는 임의의 도시에서 다른 도시로 이동하는 최단 경로를 항상 구할 수 있다.

이 최단 경로 중, 가장 긴 경로를 찾는 효율적인 방법은 무엇일까?

정렬 및 그리디로 풀 수 있을 것 같은데, 여러분들의 의견이 궁금합니다.

가령 입력이 아래와 같이 들어왔을 때, 3번 도시와 7번 도시의 거리가 12로 가장 멉니다 4 + 4 + 4(교차로 거리)
1번 도시와 3번 도시의 거리는 5+4+2 = 11 이고, 1번 도시와 5번 도시의 거리는 5+2+4 = 11 이므로 정답이 될 수 없습니다.

8
5 2 4 2 2 2 4 2

1번 도시부터 N번 도시까지 입력이 선형적으로 들어왔지만, 1번 도시로 가는 도로와 N번 도시로 가는 도로는 교차로 상에서 서로 인접합니다 (거리가 1입니다) 이 점 유의바랍니다!

[시간복잡도 O(N^2) 방법으로의 접근]
1번 도시에서 1~N번 도시 간의 거리를 구한다.
2번 도시에서 1~N번 도시 간의 거리를 구한다.
.... 이걸 N번 도시까지 반복한다.