bzoj 2599 [IOI2011]Race 點分

Time Limit: 70 Sec  Memory Limit: 128 MB

Submit: 4768  Solved: 1393

[Submit][Status][Discuss]

給一棵樹,每條邊有權.求一條簡單路徑,權值和等于K,且邊的數量最小.N <= 200000, K <= 1000000

第一行 兩個整數 n, k

第二..n行 每行三個整數 表示一條無向邊的兩端和權值 (注意點的編号從0開始)

一個整數 表示最小邊數量 如果不存在這樣的路徑 輸出-1

4 3

0 1 1

1 2 2

1 3 4

2

 2018.1.3新加資料一組，未重測