시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 15 7 7 46.667%

문제

JOI 국에는 N개의 도시가 있다. 이 도시들 사이에는 M개의 도로가 있는데 이 도로는 양방향으로 통행이 가능한 도로이다. 모든 도시들은 연결되어 있다.

현재 JOI국의 K개의 도시들에서 축제가 벌어지고 있다. JOI국의 국민들은 축제를 좋아하는 사람들도 있지만 그 분위기를 매우 싫어하는 국민들도 제법 있다.

축제를 싫어하는 사람 Q명이 도시들 사이를 이동하려고 한다. 출발도시와 도착도시가 주어질 때, 가능한 한 축제를 하는 도시와의 거리를 멀게하여 원하는 도시로 가는 방법을 구하여라. 단, 축제하는 도시와 임의의 도시와의 거리는 두 지점간의 최단경로로 계산한다.

입력

첫째 줄에 도시의 수 N, 도로의 수 M, 축제를 여는 도시의 수 K, 축제를 싫어하는 사람의 수 Q가 공백으로 구분되어 입력된다.

다음 줄부터 M줄에 걸쳐서 각 도로의 정보 시작점, 출발점, 거리가 공백으로 구분되어 입력된다. 거리는 1000을 넘지 않는다.

다음 줄 부터 K줄에 걸쳐서 축제를 하는 도시의 번호가 한 줄에 하나씩 입력된다.

다음 줄부터 Q줄에 걸쳐서 축제를 싫어하는 사람이 출발하는 출발지와 도착지가 한 줄에 하나씩 공백으로 구분되어 입력된다.

  • 2 ≤ N ≤ 100000
  • 1 ≤ M ≤ 200000
  • 1 ≤ K ≤ N
  • 1 ≤ Q ≤ 100000

출력

Q줄에 걸쳐서 입력받은 순서대로 각 사람이 이동하는데 축제하는 도시와의 최대거리를 출력한다.

예제 입력

6 6 2 3
1 2 5
2 3 4
2 4 6
3 5 9
4 5 3
5 6 7
1
6
3 4
5 2
1 4

예제 출력

7
5
0

예제 입력 2

12 17 2 5
1 3 6
1 6 7
2 3 8
2 4 4
2 8 11
2 12 2
3 6 3
3 7 8
3 11 2
4 12 2
5 10 3
6 10 5
8 9 6
8 12 7
9 10 6
11 9 10
12 9 5
8
7
2 6
5 2
1 10
8 9
9 4

예제 출력 2

8
8
11
0
6

힌트

예제 1. 3에서 4로 가는 경우는 3-5-4로 이동하면 가장 가까운 축제가 6번이고 거리는 7이다. 이 값이 최대이고, 5에서 2로 가는 경우는 5-3-2, 5-4-2 모두 1번 축제와 거리 5가 되므로 이 값을 출력한다. 마지막으로 1에서 4로 가는 경우는 1이 축제지 이므로 축제지와의 최대거리는 0이된다.

 

예제 2.

출처

Olympiad > 일본정보올림피아드 > JOI 2012 5번

  • 문제를 번역한 사람: koosaga