Score : $600$ points
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$, printYes
; otherwise, printNo
.
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$
Print $Q$ lines. The $i$-th line should contain the answer for the $i$-th problem.
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
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
.