Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5395 --小明聚会
5395: 小明聚会
警告！
题目
状态
题解
题目描述
小明住在 H 国的首都。H 国有 $n$ 个城市，其中 $1$ 号城市为其首都。城市间有 $n-1$ 条单向道路。从任意一个城市出发，都可以沿着这些单向道路一路走到首都，从任何一个城市走到首都的路径是 **唯一** 的。 想要通过某一条道路，你必须使用一次过路券。H 国一共有 $m$ 种过 路券，每张过路券以三个整数表示：$v\ k\ w$：你可以在城市 $v$ 以价格 $w$ 买到一张过路券。这张券可以使用 $k$ 次。这意味着，拿着这张券通过了 $k$ 条道路之后，这张券就不能再使用了。 请注意你同一时间最多只能拥有 **最多一张** 过路券。但你可以随时撕掉手中已有的过路券， 并且在所在的城市再买一张。 小明家在首都。他有 $q$ 位朋友，他希望把这些朋友们都邀请到他家做客。他想要知道每位朋友要花多少路费。他的朋友们永远都会选择一条花费最少的方式到达首都。 小明没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么？
输入
输入的第一行包含两个空格隔开的整数 $n$ 和 $m$，表示 H 国的城市数量和过路券的种数。 之后的 $n-1$ 行各自包含两个数 $a_i$ 和 $b_i$，代表城市 $a_i$ 到城市 $b_i$ 间有一条单向道路。 之后的 $m$ 行每行包括三个整数 $v_i,k_i$ 和 $w_i$，表示一种过路券。 下一行包含一个整数 $q$，表示小明朋友的数量。 之后的 $q$ 行各自包含一个整数，表示小明朋友所在的城市。
输出
输出共 $q$ 行，每一行代表一位朋友的路费。
样例输入输出
输入#1
复制
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
输出#1
复制
10 22 5
提示
【样例解释】 对于第一位朋友，他在 $5$ 号城市只能购买一种过路券，花费 $10$ 元并且可以使用 $3$ 次。这 足够他走到首都，因此总花费是 $10$元。 对于第二位朋友，他在 $6$ 号城市只能购买 $20$ 元的过路券，并且只能使用一次。之后，他可以在 $3$ 号城市购买 $2$ 元，可以使用 $3$ 次的过路券走到首都。总花费是 $22$ 元。 对于第三位朋友，他在 $7$ 号城市可以购买两种过路券。他可以花 $3$ 元买一张可以使用 $2$ 次的券，然后在 $3$ 号城市再买一张 $2$ 元，可以使用 $3$ 次的券，走到首都。总花费是 $5$ 元，而且其他的购买方式不会比这种更省钱。 【数据范围】 对于 $40\%$ 的数据，$n,m,q \leq 10$，$w_i \leq 10$。 另有 $20\%$ 的数据，$n,m,q \leq 500$，$w_i \leq 100$。 另有 $20\%$ 的数据，$n,m,q \leq 5 \times 10^3$，$w_i \leq 10^3$。 对于 $100\%$ 的数据，$1 \leq n,m,q \leq 10^5$，$1 \leq w_i \leq 10^4$，$1 \leq v_i,k_i \leq n$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
递交数
1
已通过
1
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和