题目描述

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

输入格式：

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

输出格式：

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

3 3
1 2 1
2 3 2
1 3 3
1 3

103.07153164

说明

1<=n<=2000

题解：

倒着跑spfa

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int fst[1100000], nxt[1100000], tot = 0;
double dis[1100000];
bool used[1100000];
int st, ed;
struct qer
{
    int from, to;
    double cost;
}es[1100000];
queue <int> q;
void build (int f, int t, double d)
{
    es[++tot] = (qer){f, t, d};
    nxt[tot] = fst[f];
    fst[f] = tot;
}
void spfa(int s)
{
    q.push(s);
    used[s] = 1;
    dis[s] = 100;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        used[u] = 0;
        for (int i = fst[u]; i; i = nxt[i])
        {
            int v = es[i].to;
            if (dis[v] > dis[u]/es[i].cost)
            {
                dis[v] = dis[u]/es[i].cost;
                if (!used[v])
                {
                    used[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int f, t;
        double d;
        scanf("%d%d%lf", &f, &t, &d);
        build (f, t, 1.0 - d/100);
        build (t, f, 1.0 - d/100);
    }
    scanf("%d%d", &st, &ed);
    for (int i = 0; i <= 2000; i++)
        dis[i] = 2147483640.0;
    spfa(ed);
    printf("%.8f", dis[st]);
    return 0;
}