0279 - JOI 国のお祭り事情 (Festivals in JOI Kingdom)

時間制限 2 秒 / メモリ制限 128 MB / 得点 100 / Writer root / x 3 / 統計 /

TLE
2sec
MLE
128MB
得点
100

問題

　JOI 国には N 個の街があり，それらの間は M 本の双方向に通行可能な道路で結ばれている．国民は道路を通ってそれらの街を移動する．
　JOI 国の国民には，お祭りが好きな人が多く，現在，K 個の街でお祭りが開催されており，非常に賑わっている．一方で，一部の国民はお祭りを騒がしいとして嫌い，お祭りにできるだけ近づきたくないと思っている．
　そこで国王は，優秀なプログラマーであるあなたに，そのようなお祭りを嫌う国民のため，ある街からある街に移動するために，お祭りが開催されている街にどれだけ近づかずに移動することができるかを高速に調べることのできるプログラムの作成を依頼した．

課題

　道路の情報とお祭りが開催されている街の情報，および Q 個のクエリ（出発する街 Si と行きたい街 Tiの組）が与えられる．各クエリi に対し，街 Si から街 Ti へのすべての経路のうち，お祭りまでの距離が最大となる経路の，お祭りまでの距離を求めるプログラムを作成せよ．ただし，ある経路のお祭りまでの距離とは，経路上の街からお祭りが開催されている街までの移動距離の最小値のことである．

制限

2 ≤ N ≤ 100 000 (= 105)     JOI 国の街の個数
1 ≤ M ≤ 200 000 (= 2 × 105)     JOI 国の道路の本数
1 ≤ K ≤ N     お祭りが開催されている街の個数
1 ≤ Q ≤ 100 000 (= 105)     クエリの個数
1 ≤ Li ≤ 1 000     i 番目の道路の長さ

入力

標準入力から以下のデータを読み込め．

  • 1 行目には整数 N, M, K, Q が空白を区切りとして書かれている．N は JOI 国の街の個数を，M は JOI 国の道路の本数を，K はお祭りが開催されている街の個数を，Q はクエリの個数をそれぞれ表す．街には 1, 2, ... , N の番号がつけられている．
  • 続く M 行は道路の情報を表す．i + 1 行目(1 ≤ i ≤ M) には整数 Ai, Bi, Li (1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N) が空白を区切りとして書かれている．これは，i 番目の道路が街 Ai と街 Bi を結んでおり，長さが Li であることを表す．道路の両端が同じ街であることはない．また，任意の2 つの街 p, q に対し，p と qを結ぶ道路は 2 本以上存在しない．どの街からどの街へもいくつかの道路をたどって行くことができる．
  • 続く K 行はお祭りが開催されている街の情報を表す．i + M + 1 行目(1 ≤ i ≤ K) には 1 つの整数 Fi(1 ≤ Fi ≤ N) が書かれている．これは街 Fi でお祭りが開催されていることを表す．F1, ..., FK の中に同じ値が 2 回以上現れることはない．
  • 続く Q 行はクエリを表す．i + M + K + 1 行目(1 ≤ i ≤ Q) には 2 つの整数 Si, Ti (1 ≤ Si ≤ N, 1 ≤ Ti ≤ N, Si ≠ Ti) が空白を区切りとして書かれている．これは i 番目のクエリの出発する街が Si であり行きたい街が Ti であることを表す．

出力

　標準出力に，全クエリへの答えを Q 行で出力せよ．すなわち，i 行目に，街 Si から街 Ti へのすべての経路のうち，お祭りまでの距離が最大となる経路の，お祭りまでの距離を表す整数を出力せよ．

採点基準

　採点用データのうち，
　配点の10% 分については，Q = 1 を満たす．
　配点の20% 分については，N ≤ 5000, Q ≤ 5 000 を満たす．
　配点の30% 分については，これら 2 つの条件の少なくとも一方を満たす．また，これら 2 つの条件の両方を満たすような採点用データはない．

入出力例

入力例 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

出力例 1

7
5
0

　6 つの街が 6 本の道路で結ばれており，お祭りは街 1, 6 の 2 つの街で開催されている．クエリは以下の 3 つである．

  • 1 つ目のクエリは街 3 から街 4 へ行くというものである．街 2 を経由する経路ではお祭りまでの距離は5，街5 を経由する経路ではお祭りまでの距離は 7 となるため，答えは 7 である．
  • 2 つ目のクエリは街 5 から街 2 へ行くというものである．街 3 と街 4 のどちらを経由しても，街 2 でお祭りまでの距離が最小となり，答えは 5 である．
  • 3 つ目のクエリは街 1 から街 4 へ行くというものである．街 1 はお祭りが開催されている街であるため，答えは 0 となる．

図1: 入力例1

入力例 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

図2: 入力例2