#Pold1022. 算法提高 金属采集

    ID: 358 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>蓝桥杯-算法提高赛制:ACM来源:蓝桥杯练习系统 ID: 21 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T21树上算法

算法提高 金属采集

算法提高 金属采集

题目描述

人类在火星上发现了一种新的金属!这些金属分布在一些奇怪的地方,不妨叫它节点好了。一些节点之间有道路相连,所有的节点和道路形成了一棵树。一共有 n 个节点,这些节点被编号为 1~n 。人类将 k 个机器人送上了火星,目的是采集这些金属。这些机器人都被送到了一个指定的着落点, S 号节点。每个机器人在着落之后,必须沿着道路行走。当机器人到达一个节点时,它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后,可以从任意一个节点返回地球。当然,回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息,包括它的两个端点 x 和 y,以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属,这个任务就交给你了。

输入格式

输入描述:

第一行包含三个整数 n, S 和 k ,分别代表节点个数、着落点编号,和机器人个数。

接下来一共 n-1 行,每行描述一条道路。一行含有三个整数 x, y 和 w ,代表在 x 号节点和 y 号节点之间有一条道路,通过需要花费 w 个单位的能量。所有道路都可以双向通行。

输入样例: 6 1 3 1 2 1 2 3 1 2 4 1000 2 5 1000 1 6 1000

输出格式

输出描述: 输出一个整数,代表采集所有节点的金属所需要的最少能量。 输出样例: 3004

数据范围

(原站未提供,导入后需人工补齐)

样例

参考上文 
参考上文

提示

HINT:时间限制:1.0s 内存限制:256.0MB

所有机器人在 1 号节点着陆。

第一个机器人的行走路径为 1->6 ,在 6 号节点返回地球,花费能量为1000。

第二个机器人的行走路径为 1->2->3->2->4 ,在 4 号节点返回地球,花费能量为1003。

第一个机器人的行走路径为 1->2->5 ,在 5 号节点返回地球,花费能量为1001。