初看此题，觉得非常简单，一道dijkstra的裸题而已，然后成功的没做出来......
若A有100块钱，向B转账，扣 5%的手续费，B得到的钱为 100 * （1 - 5%）= 95 元

正解

设 Wi = （1 - 手续费百分比）
由题意得 A * W1 * W2 * ··· * Wn = B
即 A * W1 * W2 * ··· * Wn = 100
所以要求的答案 A = 100 / (W1 * W2 * ··· * Wn)
目标是要求A的最小值，所以 W1 * W2 * ··· * Wn 值最大时，A 为最小

怎么求W1 * W2 * ··· * Wn最大呢？
将乘积取log
log（W1 * W2 * ··· * Wn）= logW1 + logW2 + ··· + logWn
因为是百分比，满足 0 <= Wi <= 1, 故所有的log结果都是负数(<= 0)
求一些负数的最大值 等价于 求它们相反数的最小值
即转换成了最短路模型

推测：求乘积最长最短啥的应满足以下条件

• 求乘积最大（本题）

  Dijkstra 需满足 0 <= w <= 1

• 求乘积最小

  Dijkstra 需满足 w >= 1

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 2100;
int n, m;
int bgn, ed;
double g[N][N];
double dist[N];
bool st[N];

void f(){
    dist[bgn] = 1;
    for(int i = 1; i <= n; ++i){
        int t = -1;
        for(int j = 1; j <= n; ++j){
            if(!st[j] && (t == -1 || dist[j] > dist[t])) t = j;
        }

        st[t] = true;

        for(int j = 1; j <= n; ++j) dist[j] = max(dist[j], dist[t] * g[t][j]);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i){
        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);
    }

    scanf("%d%d", &bgn, &ed);

    f();

    printf("%.8lf", 100 / dist[ed]);

    return 0;
}

记录一下错误思路

直接按照Dijkstra模板算出最短路径，用pre数组记录最短路经过的 路径 ，然后直接从B=100反推回去
但是没想到最短路不止有一条，而pre只能保存一条最短路的路径，连题目样例都没有过。》。