#BZOJ4987. Tree

Tree

题目描述

从前有棵树。
找出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