TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P4239
  • 問題
  • P4239追捕游戏
    制限 : 時間制限 : - MS   メモリ制限 : 265536 KB
    審判説明 : 1s
    問題説明

    何老板最近在追铺一个翻窗进机房玩游戏的同学。该学生多次趁机房没人,翻窗进入机房玩游戏,应该受到制裁。翻墙不仅危险,更是非常严重的违纪行为,但这位同学仍旧乐此不疲。

    科学馆有n个机房,机房之间n-1个窗户,窗户两面都是机房,可以双向翻阅。任意两个机房都可以通过一次或者多次翻窗相互到达。某一次,这个同学从A机房出发沿最短路线翻窗前往B机房玩游戏。在这个同学出发的同时,何老板从C机房出发翻窗去追捕那个同学。翻过每个窗户要花费固定的时间(单位秒)。这位同学和何老板翻同一个窗户的时间相同

    若这位同学到达B机房时还没有被何老板抓住,何老板就会被扣工资。何老板总共追捕m次,每次追捕开始前,何老板想知道他是否能够抓到这个同学,如果能,何老板最少需要花费多少秒?

    入力形式

    第一行,两个整数n和m

    接下来n-1行,每行三个整数X,Y,Z,表示城市X和Y之间有一条长度为Z的道路相连。

    接下来m行,每行三个整数A,B,C。

    出力形式

    m行,每行对应依次追捕的结果。若能追捕到这个同学,输出一个整数,表示何老板最少需要花费多少秒。若无法抓到这个同学,输出-1。

    サンプル入力 1

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

    サンプル出力 1

    10
    9

    サンプル入力 2

    10 2
    1 5 10
    4 6 13
    5 3 18
    5 7 15
    5 8 11
    6 9 11
    9 2 14
    10 4 13
    10 1 12
    4 3 1
    5 6 8

    サンプル出力 2

    0
    -1

    ヒント

    【样例解释】
    第1次在5号机房抓住坏人。
    第2次在4号机房抓住坏人。

    【数据范围】
    对于约40% 的数据:1≤N,M≤2000
    对于约100% 的数据:1≤N,M≤100000,1≤道路的长度≤10000


    ソース  何某造,nodgd改