TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3695
  • Problem
  • P3695清洁机器人
    Limits : Time Limit : - MS   Memory Limit : 65536 KB
    Judgment Tips : 时限1000ms
    Description

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

    Input Format

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

    Output Format

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

    Sample Input 1

    3 1 1
    1 2 1
    1 3 1

    Sample Output 1

    6

    Sample Input 2

    3 1 2
    1 2 1
    1 3 1

    Sample Output 2

    5

    Hint

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

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