← 返回题目列表

AtCoder · abc250_h

Ex. 侵入高桥

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

分数: 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.