在 nn 个人中，某些人的银行账号之间可以互相转账。
这些人之间转账的手续费各不相同。
给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 AA 最少需要多少钱使得转账后 BB 收到 100 元。
输入格式
第一行输入两个正整数 n,mn,m，分别表示总人数和可以互相转账的人的对数。
以下 mm 行每行输入三个正整数 x,y,zx,y,z，表示标号为 xx 的人和标号为 yy 的人之间互相转账需要扣除 z%z% 的手续费 ( z<100z<100 )。
最后一行输入两个正整数 A,BA,B。
数据保证 AA 与 BB 之间可以直接或间接地转账。
输出格式
输出 AA 使得 BB 到账 100 元最少需要的总费用。
精确到小数点后 8 位。
数据范围
1≤n≤20001≤n≤2000,
m≤105m≤105输入样例：
3 3 1 2 1 2 3 2 1 3 3 1 3输出样例：
103.07153164
核心思路
首先来个数学建模吧，假设A,B有一条边，他们之间的权重是w。那么A经过这条边之后他的值就变为了\(A(1-w)\).所以假设他们之间有k条边，那么就会是：\(A*w_1*w_2*w_3*..w_k=100(其中w_1=1-w_1)\).我们既然需要A最小，那么也就是需要w的乘积最大。
那么对于乘积我们可不可以使用迪杰斯特拉呢，我们可以看下w的取值范围：\(0\le w \le 1\).所以我们会联想指对互换，也就是变乘积为加法：\(ln(w_1*w_2*...w_k)=ln(w_1)+ln(w_2)+...+ln(w_k)\).
所以这要边权的范围是合适的，那么就是可以使用迪杰斯特拉的。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2200,M=200000;
double g[N][N],dist[N];//朴素版的使用这个存图更好一点,因为使用邻接矩阵代码更加短。
int st[N];
int n,m,S,T;
void dijkstra()
{
dist[S]=1;//为什么呢，因为我们加法的零元是0，乘法的是1.
// st[S]=1;这里不可以初始化的原因是，如果初始化了就不可更新后面的值了。就无法去3那里了。
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]<dist[j]))
t=j;
}
// cout<<t<<endl;
st[t]=1;
for(int j=1;j<=n;j++)//3
{
dist[j]=max(dist[j],dist[t]*g[t][j]);
}
}
}
int main()
{
cin>>n>>m;//为什么g数组不需要初始化呢，因为我们的g数组是0就已经是初始化了，因为我们这是乘法。
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
double z=(100.0-c)/100;
g[a][b]=g[b][a]=max(g[a][b],z);
}
cin>>S>>T;
dijkstra();
printf("%.8lf\n",100/dist[T]);
}