最小花费

原题链接

题目描述

在 \(n\) 个人中，某些人的银行账号之间可以互相转账。

这些人之间转账的手续费各不相同。

给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 \(A\) 最少需要多少钱使得转账后 \(B\) 收到 100 元。

---

思路

由题目可以知道，\(a\) 向 \(b\) 转账需要 \(c\%\) 的手续费，即 \(a\) 对 \(b\) 的汇率 \(g[a][b]=\cfrac{100-c}{100}\)。

那么如果 \(a\) 向 \(b\) 汇款，\(b\) 最终收到 100 元所需要的钱为 \(\cfrac{100}{g[a][b]}\)。要使所需要的钱最少，则分母需要最大。

推广向更一般的情况，需要经过多人转账。即 \(Money[A]\times \prod_{i=1}^{k} w_i=Money[B]\)。

整理式子可得，\(Money[A]=\cfrac{Money[B]}{\prod_{i=1}^{k} w_i}\)。

\(\prod_{i=1}^{k} w_i\) 即为 \(A\) 到 \(B\) 汇率的最长路。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2010;

int n, m, S, T;
double g[N][N];
double dist[N];
bool st[N];

void dijkstra() {
    dist[S] = 1;
    for (int i = 0; i < n - 1; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] < dist[j]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j++)
            dist[j] = max(dist[j], dist[t] * g[t][j]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        double z = (100.0 - c) / 100;
        g[a][b] = g[b][a] = max(g[a][b], z);
    }

    cin >> S >> T;

    dijkstra();

    cout << fixed << setprecision(8) << 100.0 / dist[T] << endl;

    return 0;
}