← 返回题目列表

AtCoder · utpc2024_m

M. 最小距离树

中文机器翻译题面 查看原题

配点 : 100 点

問題文

在顶部 编号为 1 减去 N 有 N 頂点 M 由边组成的加权简单连通无向图 G 。 i 第一条边是顶点 u_i,v_i 所连接的边的权重为 w_i 。

在顶部 编号为 1 减去 N 有 N 加权树的顶点 T ,请判断是否存在使任意 2 頂点 u,v , 您可以获得 G 以上 u-v 的最短路径长度等于 T 以上 u-v 的最短路径长度的情况。

制約

  • 所有输入均为整数
  • 2 \leq N \leq 5 \times 10^5
  • N-1 \leq M \leq 5 \times 10^5
  • 1 \leq u_i, v_i \leq N
  • 1 \leq w_i \leq 10^9
  • 给定的图很简单且连通

入力

输入是按以下格式从标准输入给出的。

N M
u_1 v_1 w_1
u_2 v_2 w_2
\vdots
u_M v_M w_M

出力

作为上述的 T 存在则 Yes 如果不存在。 步行 No 。


入力例 1

3 3
1 2 3
2 3 4
3 1 100

出力例 1

Yes

T ,顶点之间存在权重为 1,2 的边,顶点 3 的边数为 2,3 的边,顶点 4 。 3 顶点的树满足条件。


入力例 2

3 3
1 2 3
2 3 4
3 1 2

出力例 2

No

满足条件 T 不存在。例如,顶点 1,2 的边,顶点 2 的边数为 1,3 的边,顶点 2 。 3 的树,是在G 上的 1-2 的最短路径长度等于 3 ,而在这棵树上的 1-2 的最短路径长度等于 2 并不相同,因此不满足条件。