#P8273. [2017年yali集训]河取的机器人
[2017年yali集训]河取的机器人
河取的机器人(Kawashiro)
(kawashiro.cpp/c/pas)
题目描述
河城河取正在研究她的 power 收集机器人,现在到了实地检测的时候了河取的实验场地选在妖怪之山的山麓.妖怪山的山麓由 n 个路口和 n-1 条小路组成,且从任意路口出发都能通过小路到达其它任意路口.
河取会把她的 k 个机器人放在某一个路口.机器人可以沿着小路走,每一条小路只要有一个机器人走过,就可以收集小路上的所有 power.每个机器人都可以停在任意一个地方.不过,现阶段机器人移动耗能非常大,所以河城河取想知道,收集完所有的 power,机器人经过的最小距离和.
输入格式
从标准输入读入。第一行为两个整数 n,k
接下来 n-1 行,每行三个整数 s,t,v,分别代表一条小路的起点,终点和长度
输出格式
向标准输出写出。
一共 n 行 n 个整数,第 i 行的整数表示如果所有的机器人都从 i 号点出发, 经过的最小距离和
当 时,没有道路需要收集,输出 0。当 且 时,无法收集全部道路,全部 行均输出 -1。
样例输入1
5 3
1 2 8
2 3 3
3 4 14
3 5 7
样例输出1
39
35
32
39
39
数据规模与约定
对于 10%的数据,满足 n<=10,k<=2 对于 30%的数据,满足 n<=100,k<=12 对于 50%的数据,满足 n<=1000,k<=20 对于另外 10%的数据,满足 k<=2 对于 100%的数据,满足 1<=n<=100000,0<=k<=30,1<=v<=1000