题目描述
1 から N までの番号がついた N 個の地点と M 本の道があります。 i (1 ≤ i ≤ M) 番目の道は地点 ai と地点 bi を双方向に結んでいて、通過に ci 分かかります。すべての地点同士は道を何本か通って行き来出来ます。また、地点 1,…, K には家があります。
i=1,…,Q に対し、次の問題を解いてください。
地点 xi の家にいる高橋君が地点 yi の家に移動しようとしている。
高橋君は最後に睡眠を取ってから道の移動にかかった時間が ti 分を超えると移動が出来なくなる。
睡眠を取れる場所は家がある地点のみであるが、回数に制限は無い。
高橋君が地点 xi から地点 yi まで移動出来るならば Yes
と、出来ないならば No
と出力せよ。
输入格式
入力は以下の形式で標準入力から与えられる。
N M K a1 b1 c1 ⋮ aM bM cM Q x1 y1 t1 ⋮ xQ yQ tQ
输出格式
Q 行出力せよ。 i 行目には、i 番目の問題に対する出力をせよ。
题目大意
给定一张 n 个点 m 条边的无向连通简单图。每条边存在 ai,bi,ci,表示 ai→bi 或 bi→ai 耗时 ci。给定 k,定义 n 个点中只有前 k 个点有房子,q 次询问,每次给定 x,y,t,求从 x 到 y 连续的不在房子中的时间是否一定会超过 t,超过输出 No
,反之输出 Yes
。保证询问中 t 满足升序。
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
提示
制約
- 2 ≤ K ≤ N ≤ 2 × 105
- $ N-1\ \leq\ M\ \leq\ \min\ (2\ \times\ 10^5,\ \frac{N(N-1)}{2}) $
- 1 ≤ ai < bi ≤ N
- i = j ならば (ai,bi) = (aj,bj)
- 1 ≤ ci ≤ 109
- すべての地点同士は道を何本か通って行き来出来る
- 1 ≤ Q ≤ 2 × 105
- 1 ≤ xi < yi ≤ K
- $ 1\ \leq\ t_1\ \leq\ \ldots\ \leq\ t_Q\ \leq\ 10^{15} $
- 入力は全て整数
Sample Explanation 1
3 番目の問題において、地点 1 から地点 3 に直接向かうと 13 分以上かかります。しかし、 12 分かけて地点 2 に移動し、そこにある家で睡眠を取ってから地点 3 に移動することが出来ます。よって、答えは Yes
となります。