题目详情题解（0）讨论（0）提交记录（0）

AT_past202109_h.最短経路

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一张 nn 点 n−1n-1 边的无向图，第 ii 条边连接点 aia_i 和点 bib_i，长度为 cic_i。请求出是否有至少一对整数 (i,j)(i,j) 满足：从点 ii 到点 jj 的最短路径长度恰好为 xx？如果是，请输出Yes，否则请输出No。

输入格式

第一行两个整数 n,xn,x。

第二行到第 nn 行，每行三个整数 ai,bi,cia_i,b_i,c_i。

输出格式

输出Yes或No。

输入输出样例

  • 输入#1

    3 5
1 2 3
1 3 2

    输出#1

    Yes

  • 输入#2

    3 4
1 2 3
1 3 2

    输出#2

    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

说明/提示

数据规模与约定

  • 2≤n≤30002 \le n \le 3000
  • 1≤ai<bi≤n1 \le a_i \lt b_i \le n
  • 1≤ci≤1051 \le c_i \le 10^5
  • 1≤x≤1091 \le x \le 10^9
  • 保证图联通

输入解题思路，AI测评打分。不知道怎么写?

首页