题目名称	980. 最小花费
输入输出	`moneyb.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	40 MiB
测试数据	10
题目来源	Makazeu 于2012-08-05加入
开放分组	全部用户
提交状态
分类标签	图论最短路
	分享题解

通过：119，提交：268，通过率：44.4%
爆零自动机	100	0.017 s	0.31 MiB	C++
爆零自动机	100	0.024 s	0.25 MiB	C++
Youngsc	100	0.024 s	1.21 MiB	C++
爆零自动机	100	0.027 s	0.25 MiB	C++
Pine	100	0.029 s	0.68 MiB	C++
HeHe	100	0.055 s	0.59 MiB	C++
狂飙霹雳虎	100	0.071 s	2.69 MiB	C++
遥时_彼方	100	0.071 s	4.23 MiB	C++
┭┮﹏┭┮	100	0.074 s	1.76 MiB	C++
rewine	100	0.076 s	9.51 MiB	C++

关于最小花费的近10条评论(全部评论)
最短路堆优化,堆记得改成大根堆,因为是求最长路!!!!! ┭┮﹏┭┮ ┭┮﹏┭┮ 2023-08-08 12:27 8楼
本来打算膜拜一下榜一DL的代码，结果发现竟是直接输出样例答案......... 遥时_彼方 2021-11-05 21:25 7楼
真~水了一天题........ JustWB 2017-04-18 18:35 6楼
没给边数，是要我们邻接矩阵吗？ FoolMike 2016-10-15 19:50 5楼
回复 @name : 爆零自动机 2016-09-05 09:01 4楼
一开始居然爆内存了。。亲测边表开到100050可过八个点，开到200050可全A liu_runda 2016-01-26 12:15 3楼
啊吧啦吧啦吧 2015-06-14 16:09 2楼
先是直接按1-n来计算，再是不知道边的数量静态邻接表怒跪乌龙猹 2014-10-25 06:36 1楼

980. 最小花费

★★ 输入文件：moneyb.in 输出文件：moneyb.out 简单对比
时间限制：1 s 内存限制：40 MiB

【题目描述】

在$n$个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问$A$最少需要多少钱使得转账后$B$收到$100$元。

【输入格式】

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

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

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

【输出格式】

输出$A$使得$B$到账$100$元最少需要的总费用。精确到小数点后$8$位。

【样例输入】

【样例输出】

103.07153164

【数据规模】

对于100%的数据,$1<=n<=2000$;