思路：

• 题目要求从起点到终点还剩100元，求起点最少带多少钱
• 我转换为从终点出发(dist[end]=100)到起点，起点最少会有多少钱

Dijkstra(只能过样例，但不知道为什么，希望大佬帮忙看一下)

import java.io.*;
import java.util.*;

public class Main{
    private static int N = 2010;
    private static int n,m;
    private static double INF = 0x7f;
    private static double[][] g = new double[N][N];
    private static double[] dist = new double[N];
    private static boolean[] st = new boolean[N];

    private static double dijkstra(int start,int end){
        Arrays.fill(dist,INF);
        dist[start] = 100;
        for(int i = 0 ; i < n ; i++){
            int t = -1;
            for(int j = 1 ; j <= n ; j++){
                while(!st[j] && (t == -1 || dist[t] > dist[j])){
                    t = j;
                }
            }
            st[t] = true;
            for(int j = 1 ; j <= n ; j++){
                dist[j] = dist[t] / (1.0-g[t][j]);
            }
        }
        return dist[end];
    }

    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split("\\s+");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        for(int i =1 ; i <= n ; i ++){
            for(int j =1 ; j <= n ; j++){
                if(i == j) g[i][j] = 0;
                else g[i][j] = INF;
            }
        }
        for(int i = 0 ; i < m ; i++){
            s = in.readLine().split("\\s+");
            int a = Integer.valueOf(s[0]);
            int b = Integer.valueOf(s[1]);
            double c = Double.valueOf(s[2]);
            double cost = c / 100;
            g[a][b] = Math.min(g[a][b],cost);
            g[b][a] = Math.min(g[b][a],cost);
        }
        s = in.readLine().split("\\s+");
        int start = Integer.valueOf(s[0]);
        int end = Integer.valueOf(s[1]);
        double ans = dijkstra(end,start);
        System.out.printf("%.8f",ans);
    }
}

spfa(AC)

import java.io.*;
import java.util.*;

public class Main{
    private static int N = 2010 , M = 200010;
    private static int n,m,idx,INF=0x3f3f3f3f;
    private static int[] h,e,ne;
    private static double[] w = new double[M];
    private static double[] dist = new double[N];
    private static boolean[] st = new boolean[N];

    private static void add(int a,int b,double c){
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    private static double spfa(int start,int end){
        Arrays.fill(dist,INF);
        dist[start] = 100.0;
        Queue<Integer> que = new LinkedList<>();
        que.offer(start);
        st[start] = true;
        while(!que.isEmpty()){
            int t = que.poll();
            st[t] = false;
            for(int i = h[t] ; i != -1; i = ne[i]){
                int j = e[i];
                if(dist[j] > dist[t]/(1-w[i])){
                    dist[j] = dist[t]/(1-w[i]);
                    if(!st[j]){
                        que.offer(j);
                        st[j] = true;
                    }
                }
            }
        }
        return dist[end];
    }
    public static void main(String[] args)throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split("\\s+");
        n = Integer.valueOf(s[0]);
        m = Integer.valueOf(s[1]);
        h = new int[N];e = new int[M];ne = new int[M];w = new double[M];
        Arrays.fill(h,-1);
        for(int i = 0 ; i < m ; i++){
            s = in.readLine().split("\\s+");
            int a = Integer.valueOf(s[0]);
            int b = Integer.valueOf(s[1]);
            double c = Double.valueOf(s[2]);
            double cost = c / 100;
            add(a,b,cost);
            add(b,a,cost);
        }
        s = in.readLine().split("\\s+");
        int start = Integer.valueOf(s[0]);
        int end = Integer.valueOf(s[1]);
        double ans = spfa(end,start);
        System.out.printf("%.8f",ans);
    }
}