BZPRO
#4987. Tree
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
从前有棵树。
找出K个点A1，A2，…，Ak。
使得∑dis(AiAi+1),(1<=i<=K-1)最小。
输入格式
第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。
接下来n-l行每行3个非负整数x,y,z，表示从存在一条从x到y权值为z的边。
I<=k<=n。
l<x,y<=n
1<=z<=10^5
n <= 3000
输出格式
一行一个整数，表示最小的距离和。
样例
样例输入
10 7
1 2 35129
2 3 42976
3 4 24497
2 5 83165
1 6 4748
5 7 38311
4 8 70052
3 9 3561
8 10 80238
样例输出
184524
数据范围与提示
BZPRO