Dijkstra 最小花费

题目描述

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

输入格式

第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100 )。最后一行输入两个正整数 A,B。数据保证 A 与 B 之间可以直接或间接地转账。**

输出格式

输出 A 使得 B 到账 100 元最少需要的总费用。 精确到小数点后 8 位。

数据范围

1≤n≤2000, m≤105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.*;
public class Main{
    static int N=2010;
    static int M=100010;
    static int INF=0x3f3f3f3f;
    static int n,m,idx;
    static int A,B;
    static int []h=new int[N],e=new int[M*2];
    static int []ne=new int[M*2];
    static double []w=new double[M*2];
    static double []dist=new double[N];
    static boolean[]st=new boolean[N];
    public static void add(int a,int b,double c){
        e[idx]=b;
        w[idx]=c;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static double dj(){
        Arrays.fill(dist,INF);
        dist[A]=100;
        PriorityQueue<PII>q=new PriorityQueue<>();
        q.offer(new PII(A,100));
        while(q.size()!=0){
            PII t=q.poll();
            int num=t.num;
            double distence=t.distence;
            if(st[num])continue;
            st[num]=true;
            for(int i=h[num];i!=-1;i=ne[i]){
                int j=e[i];
                if(dist[j]>distence/w[i]){
                    dist[j]=distence/w[i];
                    q.offer(new PII(j,dist[j]));
                }
            }
        }
        return dist[B];
    }
    public static void main(String[]args){
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        m=scan.nextInt();
        Arrays.fill(h,-1);
        while(m-->0){
            int a=scan.nextInt();
            int b=scan.nextInt();
            int c=scan.nextInt();
            double w=(1-(double)c/100);
            add(a,b,w);
            add(b,a,w);
        }
        A=scan.nextInt();
        B=scan.nextInt();
        double t=dj();
        System.out.printf("%.8f",t);
    }
}
class PII implements Comparable<PII>{
    int num;
    double distence;
    public PII(int num,double distence){
        this.num=num;
        this.distence=distence;
    }
    public int compareTo(PII o){
        return Double.compare(distence,o.distence);
    }
}