← 返回题目列表

AtCoder · joi2012ho5

E. JOI王国的节日

中文机器翻译题面 查看原题

配点: 100 点

在JOI国家 有 N 个城市,它们之间的距离为 M 它们由一条允许双向交通的道路连接。公民通过道路在这些城市之间移动。

JOI国家的很多人都喜欢节日,目前,K 城镇正在举办节日,非常拥挤。另一方面,有些人不喜欢节日,因为他们很吵,想尽可能远离节日。

因此,国王要求你这个优秀的程序员创建一个程序,可以快速找出你可以从一个城市到另一个城市旅行多远,而无需靠近举办节日的城市,因为人们不喜欢这样的节日。

課題

举办节日的道路和城市信息,以及 Q 查询(出发城市 S_i 和您想去的城市 T_i )。每个查询 对于 i ,城市 S_i 从市区出发 编写一个程序,找出所有到 T_i 的路线中到节日距离最远的路线到节日的距离。然而,某条路线上到节日的距离是从该路线上的城镇到举办节日的城镇的最短行驶距离。

制限

2 \leqq N \leqq 100000 \,(= 10^5)  JOI国家城镇数量
1 \leqq M \leqq 200000 \,(= 2\times 10^5)  JOI 全国道路数量
1 \leqq K \leqq N  举办节日的城镇数量
1 \leqq Q \leqq 100000 \,(= 10^5)  查询数量
1 \leqq L_i \leqq 1000  i 道路长度

入力

从标准输入读取以下数据。

  • 1 行是一个整数 N, M, K, Q 以空格作为分隔符。N 是 JOI 国家/地区的城市数量,M 是JOI国家的道路数量,K 是举办节日的城镇数量,Q 表示查询次数。在城市里 它的编号为 1,2,\ldots,N 。
  • 继续 M 线代表道路信息。i + 1 行目 (1\leqq i\leqq M) 是一个整数 A_i,B_i,L_i (1\leqq A_i\leqq N,1\leqq B_i\leqq N)以空格作为分隔符。这是i 第条路是城市 A_i 和城市 B_i 长度是 L_i 。道路的两端永远不会在同一个城市。另外,任何 2 镇 对于 p, q , 连接p 和 我讨厌 q 的道路是 2 仅此而已。您可以沿着几条道路从任何一个城市前往任何一个城市。
  • 继续 K 行代表有关举办节日的城镇的信息。i + M + 1 行目 (1\leqq i\leqq K)是 1 整数 F_i (1\leqq F_i\leqq N)被写入。这是一座城市 表示 F_i 正在举办节日。 相同的值位于F_1,\ldots,F_K 中 它出现的次数不能超过 2 次。
  • 继续 Q 行代表一个查询。i + M + K + 1 行目 (1\leqq i\leqq Q) 有两个整数 S_i,T_i (1\leqq S_i\leqq N,1\leqq T_i\leqq N, S_i\neq T_i)以空格作为分隔符。这是 i 查询的起始城市为 S_i 我想去的城市是 T_i 。

出力

在标准输出上打印所有查询的答案。 输出为 Q 行。也就是说,i 线路、城市 在所有到 S_i 从市区出发 编写一个程序,找出所有到 T_i 的路线中,输出到节日距离最大的路线到节日的距离的整数。

採点基準

评分数据中,

积分分配 10 对于%,Q=1 很满意。

积分分配 20 对于%,N\leqq 5000,Q\leqq 5000 很满意。

积分分配 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 变为。