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

题目

1126. 最小花费

---

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

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

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

输入格式

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

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

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

数据保证 $A$ 与 $B$ 之间可以直接或间接地转账。

输出格式

输出 $A$ 使得 $B$ 到账 100 元最少需要的总费用。

精确到小数点后 8 位。

数据范围

$1 \le n \le 2000$ ,
$m \le 10^5$

输入样例：

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

输出样例：

103.07153164

解题

方法一：Dijkstra算法

思路

输入时把手续费转换为 $1-z\%$ 存入图中，此时该数字越大所需的手续费越低，那么要求的就是 $A \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;
}