#P1547. [USACO05MAR] Out of Hay S

    ID: 591 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图论并查集生成树贪心连通块USACO2005

[USACO05MAR] Out of Hay S

题目描述

Bessie 计划调查 NN2N20002 \leq N \leq 2\,000)个农场的干草情况,它从 11 号农场出发。农场之间总共有 MM1M1041 \leq M \leq 10^4)条双向道路,所有道路的总长度不超过 10910^9。有些农场之间存在着多条道路,所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

第一行两个整数 N,MN,M

接下来 MM 行,每行三个用空格隔开的整数 Ai,Bi,LiA_i,B_i,L_i,表示 Ai,BiA_i,B_i 之间有一条道路,长度为 LiL_i

输出格式

一个整数,表示最小生成树中的最长边的长度。

3 3
1 2 23
2 3 1000
1 3 43
43