Ex - Trespassing Takahashi 解説 /

実行時間制限: 7 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

1 から N までの番号がついた N 個の地点と M 本の道があります。 i \, (1 \leq i \leq M) 番目の道は地点 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 と出力せよ。

制約

  • 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
  • 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 番目の問題において、地点 1 から地点 3 に直接向かうと 13 分以上かかります。しかし、 12 分かけて地点 2 に移動し、そこにある家で睡眠を取ってから地点 3 に移動することが出来ます。よって、答えは Yes となります。

Score : 600 points

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.