AT_abc250_h [ABC250Ex] Trespassing Takahashi

有 $N$ 个编号为 $1$ 到 $N$ 的地点，以及 $M$ 条道路。第 $i$ 条道路连接地点 $a_i$ 和地点 $b_i$，是双向的，通行需要 $c_i$ 分钟。任意两个地点之间都可以通过若干条道路互相到达。此外，地点 $1,\ldots,K$ 上各有一所房子。 对于 $i=1,\ldots,Q$，请解答以下问题： > 高桥君现在在地点 $x_i$ 的房子里，想要前往地点 $y_i$ 的房子。 > 如果高桥君自上次睡觉后在道路上移动的时间超过 $t_i$ 分钟，则无法继续移动。 > 只有有房子的地点才能睡觉，且睡觉次数不限。 > 如果高桥君能从 $x_i$ 到 $y_i$，输出 `Yes`，否则输出 `No`。

输入按以下格式从标准输入读入。 > $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$ 个问题的答案。

### 数据范围 - $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 < b_i \leq N$ - 若 $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 < y_i \leq K$ - $1 \leq t_1 \leq \ldots \leq t_Q \leq 10^{15}$ - 所有输入均为整数 ### 样例解释 1 对于第 $3$ 个问题，若直接从地点 $1$ 前往地点 $3$，需要超过 $13$ 分钟。但可以先花 $12$ 分钟到地点 $2$，在那里有房子可以睡觉，然后再前往地点 $3$。因此，答案为 `Yes`。 由 ChatGPT 4.1 翻译