UOJ Logo Zijian Online Judge

ZOJ

#18. 开车旅行

统计

某地区的地图可以看成是一个 $n$ 个点 $m$ 条带权边的无向图,其中有 $k$ 个点是加油站,而汽车在加油站可以把油箱加满。已知 $x$ 单位的油箱在不加油的情况下最多能走 $x$ 单位的路程。

现在给定 $q$ 组询问,每次询问能否开一辆油箱容量为 $v$ 单位的汽车从点 $x$ 走到点 $y$(保证 $x、y$ 均为加油站)。

输入格式

第一行为三个正整数 $n、k、m$。

第二行为 $k$ 个互不相同的正整数 $p_1、p_2、…、p_k$,表示哪些点是加油站。

接下来的 $m$ 行每行三个正整数 $x、y、d$,描述一条从点 $x$ 到点 $y$ 长度为 $d$ 单位的双向边。

接下来一行一个正整数 $q$ 表示询问个数。

接下来的 $q$ 行每行三个正整数 $x、y、v$ 表示一个询问。

输出格式

对于每个询问,如果能输出 YES,否则输出 NO。

样例

input

6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

output

YES
YES
YES
NO

限制与约定

对于 $30\texttt{%}$ 的数据:$2 \leq k \leq n \leq 200$ ,$1 \leq m、q \leq 2000$。

另有 $30\texttt{%}$ 的数据:保证整张图是一条链。

另有 $30\texttt{%}$ 的数据:保证整张图是一棵树。

对于 $100\texttt{%}$ 的数据:$2 \leq k \leq n \leq 200000$ ,$1 \leq m、q \leq 200000$,$1 \leq p_i、x、y \leq n$,$1 \leq v、d \leq 10^9$。

时间限制:$2\texttt{s}$

空间限制:$128\texttt{MB}$