配点 : 100 点
問題文
N 点和 有 M 过道。 N 点是 直到 1 到 N 到 1 每一张都有编号, i 第二段是一个点 v_{i} 和点 u_{i} 是长度 w_{i} [米]。
斋泰君即将参加那里一场不寻常的集章活动。
内容为积分
从 a_{1} 开始并第一次按下印记后,点 a_{2} 从点
直到 a_{K} 这个想法是按顺序访问 K 位置并标记它们。
本次集章活动有等级,等级为 用
- s_{i} :=地点a_{i} 盖印后,点a_{i+1} 冲压前行驶的距离 [m] 当您定义
时, 表示为max({s_{i} | 1 ≤ i ≤ K-1}),该值越小,性能越好。
点最多由一条通道连接,且通道除点外不相交。此外,没有单向通道。从任意地点沿着路径步行即可到达所有地点。
这次集章活动的不同寻常之处在于,参与者获得了 Q 魔法石将会送给你。
每块石头都有不同的编号
上面写着 b_{1} ~ b_{Q} ,通过打破这块石头,你可以扭曲到石头上写着的数字。
破碎的石头无法再次使用。扭曲期间经过的路径是 0 以米记录。
魔法石也可以在任何地方使用。因此,如果你有相应的魔法石,你也可以直接从一个点传送到下一个点。
魔石不一定需要用完。
看看善用魔法石可以让你的成绩提高多少。
制約
- 2 \leq N \leq 300
- N-1 \leq M \leq N(N-1)/2
- 1 \leq v_i,u_i \leq N(1 \leq i \leq M)
- v_i \neq u_i(1\leq i \leq M)
- 1 \leq w_i \leq 10^9(1 \leq i \leq M)
- 2 \leq K \leq N
- 1 \leq a_i \leq N(1 \leq i \leq K)
- i \neq j 代表 a_i \neq a_j(1 \leq i,j \leq K)
- 0 \leq Q \leq N
- 1 \leq b_i \leq N(1 \leq i \leq Q)
- i \neq j 代表 b_i \neq b_j(1 \leq i,j \leq Q)
入力
输入以以下格式从标准输入提供。
N M
v_{1} u_{1} w_{1}
:
v_{M} u_{M} w_{M}
K
a_{1} ... a_{K}
Q
b_{1} ... b_{Q}
出力
采取最佳行动时 请在一行中输出max({s_i | 1 ≤ i ≤ K-1})。
入力例 1
6 5 1 2 5 1 3 2 2 4 3 2 5 2 5 6 1 3 1 3 6 2 2 4
出力例 1
3
第一点 以1开头并盖章。
那么重点 步行至3并获取印章。(s_1 = 2)
然后, 打破写有2的魔法石并找到点。 扭曲到2后,点 步行至6并获取印章。(s_2 = 3)
在这种情况下此操作是最佳的,答案是3。