TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3983
  • 题目
  • P3983[ioi2011]Race
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 3s
    问题描述

    给一棵树,每条边有权.求一条简单路径,权值和等于K,且边的数量最小.
    N <= 200000, K <= 1000000

    输入格式

    第一行 两个整数 n, k
    第二..n行 每行三个整数 表示一条无向边的两端和权值 (注意点的编号从0开始)

    输出格式

    一个整数 表示最小边数量 如果不存在这样的路径 输出-1

    样例输入 1

    4 3
    0 1 1
    1 2 2
    1 3 4

    样例输出 1

    2

    样例输入 2

    3 3
    0 1 1
    1 2 1

    样例输出 2

    -1

    样例输入 3

    11 12
    0 1 3
    0 2 4
    2 3 5
    3 4 4
    4 5 6
    0 6 3
    6 7 2
    6 8 5
    8 9 6
    8 10 7

    样例输出 3

    2