最小花费

单源最短路 T2

题目描述

P1576 最小花费 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 最小花费 - 洛谷 P1576 - Virtual Judge (csgrandeur.cn)

在 $n$ 个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 $A$ 最少需要多少钱使得转账后 $B$ 收到 $100$ 元。

输入格式

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

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

最后一行输入两个正整数 $A,B$。数据保证 $A$ 与 $B$ 之间可以直接或间接地转账。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

103.07153164

提示

$1\le n\le 2000,m\le 100000$。

思路

$a-a\ast b\%=c$ $a(1-b\%)=c$ $a=\frac{c}{1-b\%}$

从B出发, 起始费用为100, 每条路的权值是当前费用的$\frac{1}{1-z\%}$ 倍, 求到达A点的最短路径。 根据数据范围, 堆优化dijkstra是最好的。

代码

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;
const int N = 2e3 + 10, M = 2e5 + 10;
const double INF = 1e9;
typedef pair<double, int> PII;
int h[N], e[M], ne[M], idx;
double w[M];
double dist[N];
bool st[N];
int n, m;
int s, et;
 
void add(int a, int b, double c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
 
void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    for (int i = 0; i < N; i++)
        dist[i] = INF;
    q.push({100.0, et});
    dist[et] = 100.0;
    while (q.size())
    {
        auto t = q.top();
        q.pop();
 
        int ver = t.second;
        if (st[ver])
            continue;
        st[ver] = true;
 
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = min(dist[j], t.first / (1.0 - w[i]));
            if (!st[j])
                q.push({dist[j], j});
        }
    }
}
 
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        double c;
        cin >> a >> b >> c;
        c /= 100.0;
        add(a, b, c);
        add(b, a, c);
    }
    cin >> s >> et;
    dijkstra();
    cout << fixed << setprecision(8);
    cout << dist[s] << endl;
    return 0;
}