#202. 宝藏
宝藏
题目描述
有 n 个洞穴和若干候选通道,通道有长度。可任选初始洞穴,然后每次从已经到达的洞穴开通一条边到一个新洞穴,最终形成一棵树。若新洞穴在树中的深度为 d(根深度0),开通长度 L 的通道费用为 d×L。求到达所有洞穴的最小总费用。
输入格式
首行 n、m;随后 m 行 u、v、L 描述无向通道。
输出格式
输出最小总费用。
样例输入
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
样例输出
4
题意整理;原题与输入输出格式对照。
有 n 个洞穴和若干候选通道,通道有长度。可任选初始洞穴,然后每次从已经到达的洞穴开通一条边到一个新洞穴,最终形成一棵树。若新洞穴在树中的深度为 d(根深度0),开通长度 L 的通道费用为 d×L。求到达所有洞穴的最小总费用。
首行 n、m;随后 m 行 u、v、L 描述无向通道。
输出最小总费用。
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
4
题意整理;原题与输入输出格式对照。