朴素 Dijkstra

根据题意问 A 最少需要多少钱使得转账后 B 收到 100 元，且一直每次转账所花费的手续费（%）
A*（1-W1）*（1-W2）... = B(100)
若A所求最少，则需要求（1-W1）*（1-W2）...最大是多少
因此有两种思路

1. 求（1-Wi）的最大值
2. 求每次 Wi 的最小值

根据题意的数据范围可知，此题采用邻接矩阵

解法一：每次维护（1-Wi）的最大值

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int N = 2010;
    static double[][] g = new double[N][N];//存储路径信息
    static double[] dis = new double[N];//存储从start到i结点的最多剩余的值，例如：99%
    static boolean[] st = new boolean[N];//标记 i 结点是否已经找到了从 start 到达 i 结点剩余的最大值

    static int n, m = 0;
    static int start, end = 0;

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();

        for (int i = 0; i < m; i++) {
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            g[a][b] = g[b][a] = Math.max(g[a][b], (100.0 - c) / 100);//维护（1-Wi）的最大值
        }

        start = scan.nextInt();
        end = scan.nextInt();

        double num = dijstra();
        //此时 A * num = 100 -> A = 100 / num
        System.out.printf("%.8f", 100 / num);
    }

    private static double dijstra() {
        //因为是寻找最大值，所以不需要把不相连的结点的距离设置为无穷大

        //开始结点对于自己来说，不需要交手续费，所以剩余的金钱为 100%
        dis[start] = 1;

        //遍历 n 次，每次都查找剩余金钱比例最大的结点
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dis[t] < dis[j])) {
                    t = j;
                }
            }
            st[t] = true;//当前t结点已经找到了从start到t的最大（1-Wi）

            //更新剩余结点的最大值
            for (int j = 1; j <= n; j++) {
                if (dis[j] < dis[t] * g[t][j]) {
                    dis[j] = dis[t] * g[t][j];
                }
            }
        }

        return dis[end];
    }
}