시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 128 MB 140 48 38 31.405%

문제

디디플래닛에 살고 있는 주민들은 정기검진을 받으러 가려고 한다.

디디플래닛에는 총 N개의 집(1, 2, ..., N)과, M개의 병원이 있으며(N + 1, N + 2, ..., N + M), 집이 있는 구역과 병원이 있는 구역은 깊은 강으로 분리되어 있다. 이 강을 건너기 위해선 반드시 다리를 거쳐야 하는데, 다리는 모두 B개(N + M + 1, N + M + 2, ..., N + M + B) 있으며 모든 다리는 0초만에 건널 수 있다고 가정하자. 또한 디디플래닛에는 집 혹은 병원 혹은 다리를 잇는 도로가 K개 존재한다. 심지어 다리와 다리를 잇는 도로도 존재할 수 있다. 그렇지만 집과 병원사이에는 깊은 강이 있기 때문에, 집과 병원을 잇는 도로는 존재하지 않음에 유의하라.

우리는 다음과 같은 Q개의 질문에 답하여야 한다.

  • Si번집에 있는 주민이 Ei번 병원까지 가는 데 걸리는 최소한의 시간은 얼마인가?

다음 질문을 수행할 수 있는 프로그램을 만들어보자.

입력

첫째 줄에 집의 수 N, 병원의 수 M(1 ≤ N, M ≤ 10,000)과 다리의 수 B(1 ≤ B ≤ 100), 도로의 수 K(1 ≤ K ≤ 2 × 104), 질문의 수 Q(1 ≤ Q ≤ 105)가 공백으로 구분되어 주어진다.

두 번째 줄부터 K개의 줄에는 정수 a, b, Ki가 공백으로 구분되어 주어진다. 이는 지점 a와 b사이에 도로가 존재하며, 그 도로를 통과하는 데 Ki(1 ≤ Ki ≤ 109)의 시간이 소요된다는 것을 의미한다.

그 다음줄부터 Q개의 줄에는 질문의 Si와 Ei를 나타내는 정수가 공백으로 구분되어 주어진다. (1 ≤ Si ≤ N, N+1 ≤ Ei ≤ N+M)

출력

i번째 줄에 i번째 질문에 대한 답을 각각 출력하라. 만약 Si에서 Ei로 갈 수 없다면 -1을 출력해야 한다.

예제 입력 1

2 2 1 5 2
1 5 3
2 5 1
3 5 3
4 5 3
1 2 1
1 3
2 4

예제 출력 1

5
4

출처

Contest > 네블컵 > 제 1회 네블컵 C번