도망자 원숭이
시간 제한2초메모리 제한128 MB
도로 이동 시간과 도시별 지연 시간이 주어질 때, 경로의 도로 시간 합과 경로상 최대 지연 시간의 합을 최소화하는 S에서 T까지의 경로 비용을 여러 질의로 구하는 문제입니다.
문제
동물원에서 탈출한 원숭이는 시작 도시에서 도착 도시까지 가능한 한 빨리 이동하려고 한다. 이 나라는 N개의 도시와 몇몇 도시 쌍을 잇는 양방향 도로로 이루어져 있다. 각 도로를 지날 때마다 정해진 시간이 걸린다.
원숭이의 오랜 숙적인 멍멍이는 원숭이가 선택한 경로 위의 도시 중 한 곳에서 원숭이를 괴롭힌다. 시작 도시와 도착 도시도 경로에 포함된다. 도시마다 멍멍이가 원숭이를 붙잡아 둘 수 있는 시간이 다르며, 멍멍이는 그 경로에 포함된 도시들 중 가장 오래 괴롭힐 수 있는 도시를 고른다.
따라서 어떤 경로의 총 시간은 도로 이동 시간의 합에, 그 경로에 포함된 도시들의 괴롭힘 시간 최댓값을 더한 값이다. 여러 질문이 주어질 때마다 시작 도시 S에서 도착 도시 T까지 가능한 최소 총 시간을 구하시오.
네 도시 A, B, C, D가 있고 원숭이가 A에서 D로 이동한다고 하자. A-B-D의 도로 이동 시간이 100이고 A-C-D의 도로 이동 시간이 140이라면 도로만 보면 A-B-D가 더 빠르다. 하지만 네 도시의 괴롭힘 시간이 10, 80, 20, 10이라면 총 시간은 각각 180과 160이 되어 A-C-D가 더 빠르다.
입력
첫 줄에 도시의 개수 N (2 <= N <= 500), 도로의 개수 M (0 <= M <= 10,000), 질문의 개수 Q (0 <= Q <= 40,000)가 주어진다.
다음 줄에 N개의 정수가 주어진다. i번째 정수는 i번 도시에서 멍멍이가 원숭이를 괴롭힐 수 있는 시간이며, 각 값은 1 이상 10,000 이하이다.
이어서 M줄에 걸쳐 세 정수 a, b, d가 주어진다. 이는 a번 도시와 b번 도시를 잇는 양방향 도로가 있고, 그 도로의 통행 시간이 d라는 뜻이다. 여기서 1 <= a, b <= N이고, d는 1 이상 10,000 이하이다.
이어서 Q줄에 걸쳐 두 정수 S, T가 주어진다. 이는 한 질문의 출발 도시와 도착 도시이다.
출력
각 질문마다 한 줄에 S번 도시에서 T번 도시까지 도망가는 데 필요한 최소 총 시간을 출력한다. 두 도시 사이에 경로가 없으면 -1을 출력한다.