2359: 【作】【基础】最少的手续费
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
某商业银行规定，两个银行账户之间转账，银行需要收取一定的手续费，且不同的账户之间转账，手续费可能不同。
现给定 个账户中的某些账户之间互相转账的手续费（转账后另一个账户收到的费用 = 转账费用 - 手续费），请问 如果希望通过转账使得 收到 元，那么 需要准备多少钱？
输入
第一行输入两个正整数 ，分别表示总人数和可以互相转账的人的对数。()
以下 行每行输入三个正整数 ，表示编号为 的人和编号为 的人之间互相转账需要扣除 的手续费 ()。
最后一行输入两个正整数 。数据保证 与 之间可以直接或间接地转账。
输出
输出 使得 到账 元最少需要的总费用。精确到小数点后 位。
样例输入 复制
3 3
1 2 1
2 3 2
1 3 3
1 3样例输出 复制
103.07153164提示
这题的关键是每条边手续费 z% 相当于一个「放大倍率」—— 想让对方收到 100 元，走这条边要准备 100/(100-z) 倍。于是问题变成：从 A 到 B 找一条倍率乘积最小的路径，答案 = 最小倍率乘积 × 100，用模板里的 Dijkstra（乘法松弛）求解。
#include <bits/stdc++.h>
using namespace std;
/*
1.本题：求A到B转账需要准备的最少总费用
定义d[]存储：走到每个点的最小倍率乘积
在更新更短路的时候，更新某个点的倍率
2.描述无向图，且要注意读入x y z，要自己构建邻接矩阵
z%手续费：转S元，对方收到S*(100-z)/100，即倍率为100/(100-z)
3.两点之间可能有多条路径
多条路的情况下，我们保留倍率最小的那条（总费用最小）
*/
const int N = 2005;
const double INF = 1e18;
double a[N][N];//邻接矩阵，a[i][j]存储i到j转账的倍率
double d[N];//存储走到每个点的最小倍率乘积
bool f[N];//存储哪些点是确定求出最短路长度
int n,m,A,B;
int main(){
cin>>n>>m;
int x,y,z;
//读入m条边
for(int i = 1;i <= m;i++){
cin>>x>>y>>z;
//转S元收z%手续费，对方收到S*(100-z)/100
//走这条边，所需费用要放大 100/(100-z) 倍
double c = 100.0/(100-z);
//如果没有读到边，或者倍率更小
//多条边的情况下保留倍率最小的边
if(a[x][y]==0 || c < a[x][y]){
a[x][y] = c;
a[y][x] = c;
}
}
cin>>A>>B;
//dijkstra：求最小倍率乘积
for(int i = 1;i <= n;i++) d[i] = INF;
d[A] = 1.0;//出发点的倍率乘积初始为1
for(int i = 1;i <= n;i++){
int mi = -1;
//求没有确定的点的最小数下标
for(int j = 1;j <= n;j++){
if(!f[j] && (mi == -1 || d[j] < d[mi])){
mi = j;
}
}
//确定该点的倍率乘积是最小的
f[mi] = true;
//尝试mi可以去的点中，没有确定的点，是否有更小的倍率乘积
for(int j = 1;j <= n;j++){
if(!f[j]&&a[mi][j]!=0&&d[mi]*a[mi][j]<d[j]){
d[j] = d[mi] * a[mi][j];
}
}
}
//B到账100元，A需准备 d*100
printf("%.8f\n", d*100);
return 0;
}