SYZOJ - 最小花费(最短路)

题目链接:https://syzoj.com/problem/290
内存限制：128 MiB 时间限制：1000 ms

题目描述

在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

解题思路

最短路问题，dis保存的是到手后的钱数，已知最后的100，可倒着推出A刚开始的钱数。

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int u, v, w;
}e[4000005];
int f[2005], vis[2005], cnt = 0;
double dis[2005];
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s) {
    queue <int> Q;
    Q.push(s);
    dis[s] = 100.00;
    vis[s] = 1;
    while (!Q.empty()) {
        int t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int i = f[t]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] > dis[t] / (1 - e[i].w * 0.01)) {
                dis[v] = dis[t] / (1 - e[i].w * 0.01);
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    int n, m, u, v, w, s, t;
    scanf("%d%d", &n, &m);
    memset(dis, 127, sizeof(dis));
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        Add(u, v, w);
        Add(v, u, w);
    }
    scanf("%d%d", &s, &t);
    Spfa(s);
    printf("%.8lf\n", dis[t]);
    return 0;
}