TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3695
  • 题目
  • P3695清洁机器人
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

    NK中学有n间教室(编号1到n),通过n-1条双向道路相连,每条道路的长度可能不同。现在有k台清洁机器人位于s号教室,现在要安排它们去清洁所有教室。
    机器人靠燃油驱动,一台机器人清洁一个教室的耗油1升。在道路上行走时,每单位距离耗油1L。
    我们希望完成清洁作业消耗的总油量尽可能少。请你计算出这个总油量。
    作业结束时,机器人可以停留在任何位置。

    输入格式

    第一行,三个整数n,s,k
    接下来n-1行,每行三个整数a,b,c,表示教室a和教室b之间有条长度为c的道路相连。

    输出格式

    一行,一个整数,表示所求答案。

    样例输入 1

    3 1 1
    1 2 1
    1 3 1

    样例输出 1

    6

    样例输入 2

    3 1 2
    1 2 1
    1 3 1

    样例输出 2

    5

    提示

    样例1说明,机器人的活动线路为1->2->1->3,路上耗费3L燃油,清洁教室耗费3L

    1<=n<=10000, 1<=s<=N, 1<=k<=10
    1<=c<=1000000.