题目：最小花费

原题传送门

题目描述

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

输入格式
第一行输入两个正整数$n,m$，分别表示总人数和可以互相转账的人的对数。
以下m行每行输入三个正整数$x,y,z$，表示标号为$x$的人和标号为$y$的人之间互相转账需要扣除$z$%的手续费 $(z<100)$。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账。
输出格式
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
说明/提示
$1 \leq n \leq 2000，m \leq 100000$

输入输出样例
输入

输出

103.07153164

题解

仔细分析后就是一个Dijkstra算法的轻微变形
分析
首先，A 经过一些人转账后到达 B 点。每经过一个点就会扣除一部分手续费。到达B的钱数为100。

假设经过每个点后剩余的比重为 $w_i$ 显然 $ 0 \leq w_i < 1$
则经过由A到B 相当于 $A \prod_{i=0}^{n} w_i = B = 100$
*求A最小就是求$\prod_{i=0}^{n} w_i$ ($ 0 \leq w_i < 1$)最大值**
但是Dijkstra求的是最短路，是各个非负边权的累加和的最小值。
如果将加法改成乘法求出的结果是最大值吗？结果是正确的吗？
算法证明

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 2010;
double dist[N];
bool st[N];
double g[N][N];
int n,m,S,T;
void dijkstra()
{

    dist[S]=1;
    //st[S]=true;
    for(int i=0;i<n;++i){
        int t=-1;
        for(int j=1;j<=n;++j){
            if((!st[j])&&(t==-1||dist[t]<dist[j])) //dist[t] > dist[j]
            t=j;
        }
        st[t]=true;
        for(int j=1;j<=n;++j){
            dist[j]=max(dist[j],dist[t]*g[t][j]);//每次更新乘积的最大值。
            //dist[j] = min(dist[j],dist[t]+g[t][j]); //最短路的dj
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);

    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]);
}