#P1576. P1576 最小花费

P1576 最小花费

P1576 最小花费

普及/提高- | 来源:洛谷 | 原题链接

题意

nn 个人之间有 mm 对双向转账关系,每次转账扣除 z%z\% 的手续费(z<100z<100)。AA 想让 BB 恰好到账 100 元,求 AA 最少要付出的总费用,保留 8 位小数。即求 A→BA\to B 一条链上 (1−z1100)(1−z2100)⋯(1-\frac{z_1}{100})(1-\frac{z_2}{100})\cdots 的最大值 pp,答案为 100p\frac{100}{p}。

输入格式

第一行输入两个正整数 n,mn,m,分别表示总人数和可以互相转账的人的对数。

以下 mm 行每行输入三个正整数 x,y,zx,y,z,表示标号为 xx 的人和标号为 yy 的人之间互相转账需要扣除 z%z\% 的手续费 (z<100)(z<100)。

最后一行输入两个正整数 A,BA,B。数据保证 AA 与 BB 之间可以直接或间接地转账。

输出格式

输出 AA 使得 BB 到账 100100 元最少需要的总费用。精确到小数点后 88 位。

输入输出样例

样例 1 输入

3 3                                     
1 2 1
2 3 2
1 3 3
1 3

样例 1 输出

103.07153164

数据范围

1≤n≤20001\le n\le 2000,m≤100000m\le 100000;保证答案不超过 10410^4。

提示

考点:乘法权值的 Dijkstra——松弛改为 prod[u]*(1-z/100) > prod[v],从大根堆取当前乘积最大者。易错点:① 手续费率在 (0,1)(0,1) 开区间内,每乘一次严格变小,贪心正确性才成立;② 输出固定 8 位小数;③ 用浮点即可过(官方数据已保证精度),对拍时用分数/高精度核对。

三、建模套路

蜀ICP备2025119001号-1