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$ 个问题的答案。

输入输出样例 #1

输入 #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

说明/提示

数据范围

• $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 翻译