태현이는 최근에 새로 산 자전거로 등교를 하고자 한다.

학교 까지 다다르는 길 사이에는 산을 반드시 거쳐서 가야 학교에 도착할 수 있다.

따라서 무작정 보이는 길을 따라 통학했을 경우

거치게 되는 산에서의 가장 높은 위치와 가장 낮은 위치의 고도(높이)의 차이가 클 경우

자전거를 타고 올라가는 것을 알고 있기에 이 고도의 차이를 최대한 줄여서 통학에 지장이 없도록 하고자 한다.

따라서 태현이는 산에서 거치게 되는 가장 높은 위치와 가장 낮은 위치의 고도의 차이를 최소화 하고, 그리고 이 경우의 최단 경로를 찾고자 한다.

산에서의 통행 가능한 위치의 고도가 주어지고,

위치 사이에 이동할 수 있는 길과 그 길의 길이가 주어지고

태현이가 자전거를 타고 등교를 하였을 때 거치게 되는 가장 높은 위치와 가장 낮은 위치의 차이를 최소화 하고,

고도의 차이가 최소화 되었을 때 학교에 최대한 빠르게 도착하게끔 하는 경로를 구하는 프로그램을 작성하라.

예를 들어 다음과 같이 산이 있다고 하자.

위의 경우에서 태현이가 출발하는 위치는 1번이고 학교는 7번에 있으며, 나머지 위치들은 산에서의 위치이다.

위의 예제에서 1과 2사이에 1이 적혀 있는데, 1번 위치에서 2번 위치로 갈 경우 1의 시간이 걸린다는 것이다.

위의 그림에서 1에서 출발하여 2, 3, 4를 순서대로 거쳐서 7에 도착할 경우 이는 4의 시간이 걸리는 최단 경로이나,

이 경우 고도의 차이는 8이다. 하지만 5, 6, 4를 거쳐서 갈 경우 도착 시간은 11이나 고도의 차이는 2가 되어 이 경우가 답이 된다.

(6에서 7로 바로 갈 경우에 도 고도의 차이는 같으나 경로가 길어지기 때문에 답이 될 수 없다.)

자전거 timer 1s memory 128MB

자전거 1s 128MB