아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

JOI 국가의 행사

시간 제한1초메모리 제한128 MB

요약
축제 도시가 있는 연결 가중 그래프에서 두 도시 사이 경로 위 도시들의 축제까지 거리 최솟값을 최대화하는 값을 각 질의마다 구한다.
난이도

어려움10점 중 8점

유형
그래프, 최단 경로, 유니온 파인드, 정렬
정답자
아직 제출이 없습니다

문제

JOI 국에는 NN개의 도시가 있으며, 도시들은 MM개의 양방향 도로로 연결되어 있다. 모든 도시는 서로 연결되어 있어 어떤 도시에서 다른 어떤 도시로도 이동할 수 있다.

현재 KK개의 도시에서 축제가 열리고 있다. 축제를 싫어하는 사람 QQ명이 각자 출발 도시에서 도착 도시로 이동하려 한다. 어떤 도시에서 축제까지의 거리는, 그 도시에서 가장 가까운 축제 도시까지의 최단 경로 길이로 정의한다.

각 사람은 이동 경로를 자유롭게 고를 수 있다. 하나의 경로가 주어지면 그 경로 위 도시들 각각의 '축제까지의 거리' 중 가장 작은 값을 그 경로의 값이라 하자. 우리는 이 값이 최대가 되도록 경로를 고르고 싶다. 각 사람에 대해, 선택할 수 있는 경로들의 값 중 최댓값을 구하여라. 출발 도시와 도착 도시도 경로에 포함된다.

입력

첫째 줄에 도시의 수 NN, 도로의 수 MM, 축제가 열리는 도시의 수 KK, 축제를 싫어하는 사람의 수 QQ가 공백으로 구분되어 주어진다.

이어지는 MM개의 줄에는 각 도로의 정보가 출발 도시, 도착 도시, 거리 순으로 공백으로 구분되어 주어진다. 거리는 11 이상 10001000 이하이다.

이어지는 KK개의 줄에는 축제가 열리는 도시의 번호가 한 줄에 하나씩 주어진다. 축제가 열리는 도시의 번호는 서로 중복되지 않는다.

이어지는 QQ개의 줄에는 각 사람의 출발 도시와 도착 도시가 한 줄에 하나씩 공백으로 구분되어 주어진다. 출발 도시와 도착 도시는 서로 다르다.

출력

QQ개의 줄에 걸쳐, 입력된 순서대로 각 사람이 얻을 수 있는 값(경로 위 도시들의 '축제까지의 거리' 중 최솟값을 최대화한 값)을 출력한다.

제한

  • 2≤N≤100 0002 \le N \le 100\,000
  • 1≤M≤200 0001 \le M \le 200\,000
  • 1≤K≤N1 \le K \le N
  • 1≤Q≤100 0001 \le Q \le 100\,000

힌트

아래 그림은 예시에 등장하는 도로망을 나타낸다. 그림 1은 첫 번째 예시, 그림 2는 두 번째 예시의 도로망이다.

예제2

  1. 예제 1

    입력
    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. 예제 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
    예상 출력
    8
8
11
0
6