侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【最短路, Dijkstra算法】最小花费

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 15 阅读 / 590 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1126. 最小花费


nn 个人中,某些人的银行账号之间可以互相转账。

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

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

输入格式

第一行输入两个正整数 n,mn,m ,分别表示总人数和可以互相转账的人的对数。

以下 mm 行每行输入三个正整数 x,y,zx,y,z ,表示标号为 xx 的人和标号为 yy 的人之间互相转账需要扣除 z%z\% 的手续费 ( z<100z<100 )。

最后一行输入两个正整数 A,BA,B

数据保证 AABB 之间可以直接或间接地转账。

输出格式

输出 AA 使得 BB 到账 100 元最少需要的总费用。

精确到小数点后 8 位。

数据范围

1n20001 \le n \le 2000 ,
m105m \le 10^5

输入样例:

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

输出样例:

103.07153164

解题

方法一:Dijkstra算法

思路

输入时把手续费转换为 1z%1-z\% 存入图中,此时该数字越大所需的手续费越低,那么要求的就是 ABA \to B 的最短路(定义权值越大越短),使用 Dijkstra 算法求解即可。

注意:在进行松弛操作时要把权值相乘而非相加。

代码

#include <iostream>

using namespace std;

const int N = 2010, M = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m;
double g[N][N], dists[N];
bool vis[N];

double dijkstra(int ori, int dest) {
    dists[ori] = 1;
    for (int i = 1; i < n; ++i) {
        int mn = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && (mn == -1 || dists[j] > dists[mn])) mn = j;
        }
        vis[mn] = true;
        for (int j = 1; j <= n; ++j) {
            dists[j] = max(dists[j], dists[mn] * g[mn][j]);
        }
    }
    return dists[dest];
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        double rate = (100 - w) / 100.0;
        g[u][v] = g[v][u] = max(g[u][v], rate);
    }
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%.8lf", 100 / dijkstra(a, b));
    
    return 0;
}
0

评论区