102507: [AtCoder]ABC250 Ex - Trespassing Takahashi

Problem Statement

There are $N$ points numbered $1$ through $N$, and $M$ roads. The $i$-th ($1 \leq i \leq M$) road connects Point $a_i$ and Point $b_i$ bidirectionally and requires $c_i$ minutes to pass through. One can travel from any point to any other point using some number of roads. There is a house on Points $1,\ldots, K$.

For $i=1,\ldots,Q$, solve the following problem.

Takahashi is currently at the house at Point $x_i$ and wants to travel to the house at Point $y_i$.
Once $t_i$ minutes have passed since his last sleep, he cannot continue moving anymore.
He can get sleep only at a point with a house, but he may do so any number of times.
If he can travel from Point $x_i$ to Point $y_i$, print Yes; otherwise, print No.

Constraints

• $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$, then $(a_i,b_i) \neq (a_j,b_j)$.
• $1 \leq c_i \leq 10^9$
• One can travel from any point to any other point using some number of roads.
• $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}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $i$-th line should contain the answer for the $i$-th problem.

Sample Input 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

Sample Output 1

No
Yes
Yes

In the $3$-rd problem, it takes no less than $13$ minutes from Point $1$ to reach Point $3$ directly. However, he can first travel to Point $2$ in $12$ minutes, get sleep in the house there, and then travel to Point $3$. Thus, the answer is Yes.

问题描述

有N个编号为1到N的点，以及M条道路。第i条（1≤i≤M）道路双向连接点a_i和点b_i，通过该道路需要c_i分钟。可以通过一些道路从任何一个点到达任何一个点。1到K的点上有一个房子。

对于i=1,...,Q，解决以下问题。

高桥现在位于编号为x_i的房子，他想前往编号为y_i的房子。
自从他上次睡觉以来，一旦过了t_i分钟，他就不能再继续移动了。
他只能在有房子的点上睡觉，但他可以睡任意多次。
如果他能从点x_i到达点y_i，打印Yes；否则，打印No。

约束条件

• 2≤K≤N≤2×10^5
• N-1≤M≤min(2×10^5，N(N-1)/2)
• 1≤a_i＜b_i≤N
• 如果i≠j，那么(a_i,b_i)≠(a_j,b_j)。
• 1≤c_i≤10^9
• 可以通过一些道路从任何一个点到达任何一个点。
• 1≤Q≤2×10^5
• 1≤x_i＜y_i≤K
• 1≤t_1≤...≤t_Q≤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个问题中，从点1直接到达点3需要至少13分钟。但是，他可以先在12分钟内到达点2，在那里睡觉，然后前往点3。因此，答案是Yes。