시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1.5 초 | 256 MB | 405 | 134 | 95 | 28.190% |
디디플래닛에 살고 있는 주민들은 정기검진을 받으러 가려고 한다.
디디플래닛에는 총 N개의 집(1, 2, ..., N)과, M개의 병원이 있으며(N + 1, N + 2, ..., N + M), 집이 있는 구역과 병원이 있는 구역은 깊은 강으로 분리되어 있다. 이 강을 건너기 위해선 반드시 다리를 거쳐야 하는데, 다리는 모두 B개(N + M + 1, N + M + 2, ..., N + M + B) 있으며 모든 다리는 0초만에 건널 수 있다고 가정하자. 또한 디디플래닛에는 집 혹은 병원 혹은 다리를 잇는 도로가 K개 존재한다. 심지어 다리와 다리를 잇는 도로도 존재할 수 있다. 그렇지만 집과 병원사이에는 깊은 강이 있기 때문에, 집과 병원을 잇는 도로는 존재하지 않음에 유의하라.
우리는 다음과 같은 Q개의 질문에 답하여야 한다.
다음 질문을 수행할 수 있는 프로그램을 만들어보자.
첫째 줄에 집의 수 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을 출력해야 한다.
2 2 1 5 2 1 5 3 2 5 1 3 5 3 4 5 3 1 2 1 1 3 2 4
5 4
Contest > BOJ User Contest > 네블컵 > 제1회 네블컵 C번