/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
AtCoder 国には 1 から N の番号がついた N 個の都市と 1 から N-1 の番号がついた N-1 本の道路があり、全ての都市同士は互いに行き来することができます。
道路 i は 都市 a_i と都市 b_i を双方向に結ぶ長さ c_i キロメートルの道路です。
正の整数 X が与えられるので、次の条件を満たす相異なる都市の組 (i,j) が存在するか判定して、存在する場合は Yes を、存在しない場合は No を出力してください。
- 都市 i から都市 j へ道路を利用して最短距離で移動したときの経路の長さが X キロメートルになる。
制約
- 2 \leq N \leq 3000
- 1 \leq a_i \lt b_i \leq N
- 全ての都市同士は互いに行き来できる。
- 1 \leq c_i \lt 10^5
- 1 \leq X \leq 10^9
- 入力中の全ての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
出力
条件を満たす都市の組が存在する場合は Yes を、存在しない場合は No を出力せよ。
入力例 1
3 5 1 2 3 1 3 2
出力例 1
Yes
都市 2 から都市 3 への最短経路は 5 キロメートルで、これは条件を満たします。よって Yes を出力します。
入力例 2
3 4 1 2 3 1 3 2
出力例 2
No
最短経路の長さが 4 キロメートルであるような都市の組は存在しません。よって No を出力します。
入力例 3
10 15 3 8 3 5 9 3 6 7 1 7 8 1 2 8 5 2 4 5 4 9 3 1 4 5 1 10 2
出力例 3
Yes
Score : 6 points
Warning
Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
The Republic of AtCoder has N cities numbered 1 through N and N-1 roads numbered 1 through N-1, where it is possible to travel between every pair of cities.
Road i connects Cities a_i and b_i bidirectionally and has a length of c_i kilometers.
Given a positive integer X, determine whether there is a pair of different cities (i, j) satisfying the condition below. If it exists, print Yes; otherwise, print No.
- The shortest path from City i to City j using roads has the length of X kilometers.
Constraints
- 2 \leq N \leq 3000
- 1 \leq a_i \lt b_i \leq N
- It is possible to travel between every pair of cities.
- 1 \leq c_i \lt 10^5
- 1 \leq X \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
a_1 b_1 c_1
\vdots
a_{N-1} b_{N-1} c_{N-1}
Output
If there is a pair of cities (i, j) satisfying the condition, print Yes; otherwise, print No.
Sample Input 1
3 5 1 2 3 1 3 2
Sample Output 1
Yes
The shortest path from City 2 to City 3 has the length of 5 kilometers, meeting the requirement, so you should print Yes.
Sample Input 2
3 4 1 2 3 1 3 2
Sample Output 2
No
There is no pair of cities such that the shortest path between them has the length of 4 kilometers, so you should print No.
Sample Input 3
10 15 3 8 3 5 9 3 6 7 1 7 8 1 2 8 5 2 4 5 4 9 3 1 4 5 1 10 2
Sample Output 3
Yes