#Pmp112. 6.小明聚会
6.小明聚会
6.小明聚会
题目描述
小明住在 H 国的首都。H 国有n个城市,其中1号城市为其首都。城市间有n-1条单向道路。从任意一个城市出发,都可以沿着这些单向道路一路走到首都,从任何一个城市走到首都的路径是唯一的。
想要通过某一条道路,你必须使用一次过路券。H 国一共有m种过 路券,每张过路券以三个整数表示:v,k,w:你可以在城市v以价格w买到一张过路券。这张券可以使用k次。这意味着,拿着这张券通过了条道路之后,这张券就不能再使用了。
请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券, 并且在所在的城市再买一张。 小明家在首都。他有q位朋友,他希望把这些朋友们都邀请到他家做客。他想要知道每位朋友要花多少路费。他的朋友们永远都会选择一条花费最少的方式到达首都。
小明没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么?
输入格式
输出格式
输出共q行,每一行代表一位朋友的路费。
数据范围
(原站未提供,导入后需人工补齐)
样例
7 7
3 1
2 1
7 6
6 3
5 3
4 3
7 2 3
7 1 1
2 3 5
3 6 2
4 2 4
5 3 10
6 1 20
3
5
6
7
10
22
5
提示
样例解释
对于第一位朋友,他在号5城市只能购买一种过路券,花费10元并且可以使用3次。这 足够他走到首都,因此总花费是10元。
对于第二位朋友,他在6号城市只能购买20元的过路券,并且只能使用一次。之后,他可以在3号城市购买2元,可以使用3次的过路券走到首都。总花费是22元。
对于第三位朋友,他在7号城市可以购买两种过路券。他可以花3元买一张可以使用2次的券,然后在3号城市再买一张2元,可以使用3次的券,走到首都。总花费是5元,而且其他的购买方式不会比这种更省钱。
对于40%的数据:;
另有20%的数据:;
另有20%的数据:;
对于100%的数据:。