分数: 600 点
问题陈述
有 N 点编号 1 通过 N,和 M 道路。 的 i-th (1 \leq i \leq M) 道路连接点 a_i 和点 b_i 双向且要求 c_i 分钟通过。 人们可以使用一定数量的道路从任何一点前往任何其他点。 Points上有一栋房子 1,\ldots, K.
对于 i=1,\ldots,Q,解决以下问题。
Takahashi 目前在 Point 的房子里 x_i 想要前往 Point 的房子 y_i.
一次 t_i 距离他上次睡觉已经过去了几分钟,他无法再继续移动。
他只能在有房子的地方睡觉,但他可以这样做任意多次。
如果他可以从 Point 出发 x_i 指向 y_i,打印Yes;否则,打印No.
约束
- 2 \leq K \leq N \leq 2 \times 10^5
- N-1 \leq M \leq \min (2 \times 10^5, \frac{N(N-1)}{2})
- 1 \leq a_i \lt b_i \leq N
- If i \neq j,然后 (a_i,b_i) \neq (a_j,b_j).
- 1 \leq c_i \leq 10^9
- 人们可以使用一定数量的道路从任何一点行驶到任何其他点。
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq x_i \lt y_i \leq K
- 1 \leq t_1 \leq \ldots \leq t_Q \leq 10^{15}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M K a_1 b_1 c_1 \vdots a_M b_M c_M Q x_1 y_1 t_1 \vdots x_Q y_Q t_Q
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 i- 第一个问题。
示例输入 1
6 6 3 1 4 1 4 6 4 2 5 2 3 5 3 5 6 5 1 2 15 3 2 3 4 2 3 5 1 3 12
示例输出 1
No Yes Yes
在 3-rd问题,需要不少于 13 距 Point 分钟 1 到达点
直接 3 。 不过,他可以先前往Point 2 in 12 分钟,在那儿的房子里睡觉,然后前往Point 3。 因此,答案是 Yes.