【例4-4】最小花费

题目描述

给定 $n$ 个人的转账网络（ $1\le n\le 2000$ ）， $m$ 条无向边 $(x,y,z)$ 表示 $x$ 与 $y$ 互相转账要扣 $z%$ 手续费（ $z<100$ ）。钱沿一条路径每过一条 $(u,v,z)$ 就被扣掉 $z%$ ，给定起点 $A$ 和终点 $B$ （保证可达），求 $A$ 至少转出多少钱，才能让 $B$ 到账恰好 100 元。答案保留 8 位小数。

输入：第一行 $n,m$ ；接着 $m$ 行 x y z；最后一行 A B。

输出：A 最少需要的总费用，精确到小数点后 8 位。

样例：

text

输出：103.07153164。

思路

把手续费 $z%$ 的边换算成"放大因子" $w=100/(100-z)>1$ ， $A$ 最少转出金额 $=100\times$ 路径上 $w$ 的连乘；连乘最小等价于对数域非负权和最小，直接在倍数上跑二叉堆 Dijkstra，dist[A]=1，答案 dist[B]*100 即输出。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 06:08
# update_at: 2026-09-30 06:08

import sys
from heapq import heappop, heappush


def dijkstra(adj: list[list[tuple[int, float]]], start: int) -> list[float]:
    """从 start 出发到每个点的“最少放大倍数”：边权是 >1 的乘法因子。"""
    dist = [float("inf")] * len(adj)
    dist[start] = 1.0                        # 不转账金额不变，起点的倍数为 1
    heap = [(1.0, start)]
    while heap:
        factor, u = heappop(heap)
        if factor > dist[u]:                # 过期堆元素，早已被更小倍数覆盖
            continue
        for v, w in adj[u]:
            relaxed = factor * w            # 再过一条手续费 z% 的边累计的倍数
            if relaxed < dist[v]:
                dist[v] = relaxed
                heappush(heap, (relaxed, v))
    return dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: list[list[tuple[int, float]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        x, y, z = next(data), next(data), next(data)
        # 手续费扣 z%：寄出 100/(100-z) 元对方才到账 100 元，故边权是这个比值
        adj[x].append((y, 100 / (100 - z)))
        adj[y].append((x, 100 / (100 - z)))

    A, B = next(data), next(data)
    dist = dijkstra(adj, A)
    print(f"{dist[B] * 100:.8f}")            # B 到手 100 元，A 至少出 倍数×100


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:46
 * update_at: 2026-10-05 10:46
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2005;
const int MAXM = 200005; // n=2000、m≈10^5，留出正反边后约 2*10^5

// 邻接表存无向图：第 i 条边从 head[u] 串起来
int head[MAXN];
int to[MAXM];
int nxt[MAXM];
double weight[MAXM]; // 边 (x,y,z) 的"放大因子" = 100/(100-z)
int edge_cnt;

void add_edge(int u, int v, double w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

int n, m;
int start_node, end_node;

// dist[u] 表示让 u 到账 1 元时，A 至少需要出的金额倍数；初值 1
double dist_val[MAXN];

void dijkstra() {
    for (int i = 1; i <= n; i++) dist_val[i] = 1e100;
    dist_val[start_node] = 1.0;
    // 小根堆：取当前倍数最小的点继续扩展
    priority_queue<pair<double,int> > heap;
    heap.push(make_pair(-1.0, start_node));
    while (!heap.empty()) {
        double cur_factor = -heap.top().first;
        int u = heap.top().second;
        heap.pop();
        if (cur_factor > dist_val[u]) continue; // 过期堆元素，跳过
        if (u == end_node) return;              // 已经取出终点，最优倍数确定
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            double relaxed = cur_factor * weight[i]; // 再过一条边累计的倍数
            if (relaxed < dist_val[v]) {
                dist_val[v] = relaxed;
                heap.push(make_pair(-relaxed, v));
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        // 手续费扣 z% 的边，对方到手 100 元要出 100/(100-z) 元，记成这个放大因子
        double factor = 100.0 / (100 - z);
        add_edge(x, y, factor);
        add_edge(y, x, factor);
    }
    cin >> start_node >> end_node;

    dijkstra();
    // B 到手 100 元，A 至少出 dist[B] * 100 元，保留 8 位小数
    cout << fixed << setprecision(8) << dist_val[end_node] * 100.0 << "\n";

    return 0;
}

【例4-4】最小花费

目录

题目描述

思路

参考代码