Problemas
태현이는 최근에 새로 산 자전거로 등교를 하고자 한다.
학교 까지 다다르는 길 사이에는 산을 반드시 거쳐서 가야 학교에 도착할 수 있다.
따라서 무작정 보이는 길을 따라 통학했을 경우
거치게 되는 산에서의 가장 높은 위치와 가장 낮은 위치의 고도(높이)의 차이가 클 경우
자전거를 타고 올라가는 것을 알고 있기에 이 고도의 차이를 최대한 줄여서 통학에 지장이 없도록 하고자 한다.
따라서 태현이는 산에서 거치게 되는 가장 높은 위치와 가장 낮은 위치의 고도의 차이를 최소화 하고, 그리고 이 경우의 최단 경로를 찾고자 한다.
산에서의 통행 가능한 위치의 고도가 주어지고,
위치 사이에 이동할 수 있는 길과 그 길의 길이가 주어지고
태현이가 자전거를 타고 등교를 하였을 때 거치게 되는 가장 높은 위치와 가장 낮은 위치의 차이를 최소화 하고,
고도의 차이가 최소화 되었을 때 학교에 최대한 빠르게 도착하게끔 하는 경로를 구하는 프로그램을 작성하라.
예를 들어 다음과 같이 산이 있다고 하자.
위의 경우에서 태현이가 출발하는 위치는 1번이고 학교는 7번에 있으며, 나머지 위치들은 산에서의 위치이다.
위의 예제에서 1과 2사이에 1이 적혀 있는데, 1번 위치에서 2번 위치로 갈 경우 1의 시간이 걸린다는 것이다.
위의 그림에서 1에서 출발하여 2, 3, 4를 순서대로 거쳐서 7에 도착할 경우 이는 4의 시간이 걸리는 최단 경로이나,
이 경우 고도의 차이는 8이다. 하지만 5, 6, 4를 거쳐서 갈 경우 도착 시간은 11이나 고도의 차이는 2가 되어 이 경우가 답이 된다.
(6에서 7로 바로 갈 경우에 도 고도의 차이는 같으나 경로가 길어지기 때문에 답이 될 수 없다.)
Entrada
첫 번째 줄에는 위치의 개수를 나타내는 N(1≤N≤100)과 길의 개수를 나타내는 M(0≤M≤5,000)이 공백을 사이에 두고 주어진다.
위치는 1부터 N까지 번호가 매겨지게 된다. 그 다음 N개의 줄에는 1번 위치부터 N번 위치까지 고도가 주어지며 이 값은 1,000,000,000 이하이다. 마지막으로 M개의 줄에는 매 줄마다 길의 정보가 주어지며,
길의 정보는 한줄에 3개의 숫자 a, b (1≤a,b≤N)와 c(1≤c≤1,000,000)이 각 숫자마다 공백을 사이에 두고 주어지는데,
이는 위치 a와 b가 이어져 있으며 오가는데 c만큼의 시간이 걸린다다는 것이다. 또한 a에서 b로 이동할 수 있으며, b에서 a로 이동할 수 있다. 처음 태현이가 시작하게 되는 위치의 번호는 1이고, N번째 위치엔 학교가 위치해 있다.
Salida
출력은 한 줄로 이루어지는데 고도의 차이가 최소 일 때의 고도차와 이 경우의 최단 경로의 값을 공백을 사이에 두고 출력한다.
Ejemplo
7 9
4
9
1
3
3
5
4
1 2 1
2 3 1
3 4 1
4 7 1
1 5 4
5 6 4
6 7 4
5 3 2
6 4 2
2 11
Debes iniciar sesión para escribir código.