#P1576. P1576 最小花费
P1576 最小花费
P1576 最小花费
普及/提高- | 来源:洛谷 | 原题链接
题意
个人之间有 对双向转账关系,每次转账扣除 的手续费()。 想让 恰好到账 100 元,求 最少要付出的总费用,保留 8 位小数。即求 一条链上 的最大值 ,答案为 。
输入格式
第一行输入两个正整数 ,分别表示总人数和可以互相转账的人的对数。
以下 行每行输入三个正整数 ,表示标号为 的人和标号为 的人之间互相转账需要扣除 的手续费 。
最后一行输入两个正整数 。数据保证 与 之间可以直接或间接地转账。
输出格式
输出 使得 到账 元最少需要的总费用。精确到小数点后 位。
输入输出样例
样例 1 输入
3 3
1 2 1
2 3 2
1 3 3
1 3
样例 1 输出
103.07153164
数据范围
,;保证答案不超过 。
提示
考点:乘法权值的 Dijkstra——松弛改为 prod[u]*(1-z/100) > prod[v],从大根堆取当前乘积最大者。易错点:① 手续费率在 开区间内,每乘一次严格变小,贪心正确性才成立;② 输出固定 8 位小数;③ 用浮点即可过(官方数据已保证精度),对拍时用分数/高精度核对。