在 n 个人中,某些人的银行账号之间可以互相转账,每次转账都需要支付不同的手续费。

给定这些人之间转账的手续费情况,请计算出最少需要多少钱使得 A 能够将 100 元转账给 B。

输入格式:

  • 第一行包含两个正整数 n 和 m,分别表示总人数和可以互相转账的人的对数。
  • 接下来的 m 行,每行包含三个正整数 x、y、z,表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 的手续费 (z < 100)。
  • 最后一行包含两个正整数 A 和 B,表示需要从 A 转账给 B。

输出格式:

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

数据范围:

  • 1 ≤ n ≤ 2000
  • 1 ≤ m ≤ 1e5

输入样例:

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

输出样例:

103.07153164

题目分析

若将答案用 X,汇率用 e 来表示, 可得出此式: 100 = X * (e1 * e2 * ··· * ei) 要使 X 最小,那么就要使 (e1 * e2 * ··· * ei)。 这道题就可以抽象为 最长路问题,可以使用 SPFA 算法。 可不可以用 Dijikstra 呢? 继续分析,我们对 (e1 * e2 * ··· * ei) 整体取对数可以发现 log (e1 * e2 * ··· * ei) = log e1 + log e2 + ··· + log ei ,由于 en >= 0 && en <= 1, 所以, 此题可以抽象为 边权全为负的最短路问题。 那么,我们可以使用 Dijikstra, 并且可以直接修改标准Dijikstra的判断条件为求最长路。

代码实现(Dijikstra)

#include <iostream>
#include <bitset>
using namespace std;
using DOU = double;
const int N = 2e3 + 10;

int n, m, s, e;
DOU dist[N], g[N][N];
bitset <N> st;
DOU dijkstra() {
    dist[s] = 1;
    for (int i = 1; i < n; ++i) {
        int t = -1;
        for (int j = 1; j <= n; ++j) 
            if (!st[j] && (t == -1 || dist[t] < dist[j]))
                t = j;
        st[t] = 1;
        for (int j = 1; j <= n; ++j)
            dist[j] = max(dist[j], dist[t] * g[t][j]);
    }
    return 100.0 / dist[e];
}
int main () {
    cin >> n >> m;
    while(m--) {
        int a, b, c;
        cin >> a >> b >> c;
        DOU charge = (100 - c) / 100.0;
        g[a][b] = g[b][a] = max(g[a][b], charge);
    }
    cin >> s >> e;
    printf("
    return 0;
}
分类: Dijkstra

1 条评论

Tourist · 2023年10月12日 上午7:13

Hello! I’m at work surfing around your blog from my new iphone 4!
Just wanted to say I love reading through your blog and look forward to all your posts!
Carry on the outstanding work!

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status