1126 最小花费（单源最短路径扩展）

深碍√TFBOYSˉ_ 2022-09-16 00:15 153阅读 0赞

**1. 问题描述：**

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

**输入格式**

第一行输入两个正整数 n，m，分别表示总人数和可以互相转账的人的对数。以下 m 行每行输入三个正整数 x，y，z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100 )。最后一行输入两个正整数 A，B。数据保证 A 与 B 之间可以直接或间接地转账。

**输出格式**

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

**数据范围**

1 ≤ n ≤ 2000，  
m ≤ 10 ^ 5

**输入样例：**

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

**输出样例：**

103.07153164  
来源：[https://www.acwing.com/problem/content/description/1128/][https_www.acwing.com_problem_content_description_1128]

**2. 思路分析：**

分析题目可以知道已知n个点m条边的无向图，每条边有一个权重相当于是汇率，我们需要求解A至少向B转多少钱使得B收到100元，A到B可以经过多个点，也即求解d(B) = d(A)w1w2...wk，d(B) = 100，要想使得d(A)最小那么应该使得w1w2...wk最大，所以本质上是在无向图中求解以A为起点B为终点所有路径的w1w2...wk的最大值，我们知道最短路径求解的是从起点到终点的最小值，以某个中间点k到达某个点的距离更小那么就更新起点到这个点的最短距离d(j) <== d(k) + w，所以我们能否借助于类似的方法来更新d(j) <== d(k) \* w，答案是可以的，因为到某个点的乘积为w1w2...wk，可以对其取一个log，那么乘积就就变成了加的形式，logw1w2...wk = logw1 + logw2 + ...logwk，而0 < wi <= 1，log函数在\[0, 1\]之间是小于等于0的我们可以对整个相乘的结果取一个负数，那么整个求解的就是log函数的最小值，也即单源最短路径，最终的结果再取一个负数那么表示的就是乘积的最大值，所以我们是可以将加号变成乘号的，在实际的实现中可以直接求解到达某个点权重乘积的最大值即可。因为每一条边的权重都是大于0小于等于1的所以当我们计算乘积最大值的时候相当于没有负权边的无向图（因为当前点权重的乘积为起点到其余点的乘积最大值之后这个点可以被用来更新其他的点并且这个点在后面的时候就不会再更新了，因为边数越多，乘以小于0的数就越多那么结果就越小所以只能够被更新一次），可以使用Dijkstra朴素版本，Dijkstra的堆优化版或者是spfa算法。扩展：如果求解的是边权乘积最小值呢？分为以下两种情况（如果是负数那么问题就变得很复杂了，因为乘以一个负数之后那么最小数变成了最大数，最大数变成了最小数，需要同时维护最短路径和最长路径，下面讨论的都是边权大于0等于0的情况）：

*  边权都大于1，因为求解的是乘积最小，所以经过的边尽可能少那么乘积是越小的，所以相当于是没有负权边的最短路径问题，每一个点作为从起点到其余点的乘积最小的点只能够被选择一次，也即只能够被更新一次，可以使用Dijkstra的朴素版本，Dijkstra算法的堆优化版，spfa算法
 *  边权有大于0小于等于1的也有大于1的，这个时候相当于是存在负权边的最短路径问题，因为乘以一个大于0小于1的数是使得结果变得更小的所以之前更新过的点还可能被再次更新，所以只能够使用spfa算法

**3. 代码如下：**

**每一个g\[i\]是一个字典相当于是邻接表：**

from typing import List
    
    
    class Solution:
        def dijkstra(self, s: int, t: int, n: int, g: List[dict]):
            # dist[i]为0表示最小值
            dis = [0] * (n + 1)
            # 因为求解的是相乘结果是最大的所以起点必须是1
            dis[s] = 1
            vis = [0] * (n + 1)
            for i in range(n):
                k = -1
                for j in range(1, n + 1):
                    if vis[j] == 0 and (k == -1 or dis[k] < dis[j]):
                        k = j
                vis[k] = 1
                for next in g[k].items():
                    if vis[next[0]] == 0 and dis[next[0]] < dis[k] * next[1]:
                        dis[next[0]] = dis[k] * next[1]
            return dis[t]
    
        def process(self):
            n, m = map(int, input().split())
            # 这里的每一个g[i]相当于是一个邻接表
            g = [dict() for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                c = (100 - z) / 100
                # 因为是无向图所以需要建两次边, 表示相互可以到达, 后面在输入起点和终点的时候也是随便输出的也即无序的, 如果没有建两次边后面会报异常
                if y in g[x]:
                    # 先转换汇率
                    g[x][y] = c
                else:
                    g[x][y] = c
                if x in g[y]:
                    # 先转换汇率
                    g[y][x] = max(g[y][x], c)
                else:
                    g[y][x] = c
            s, t = map(int, input().split())
            # 使用format函数格式化输出, 100 = d(A) * w1w2..wk, d(A) = 100 / (w1w2...wk)
            return "{:.8f}".format(100 / self.dijkstra(s, t, n, g))
    
    
    if __name__ == "__main__":
        print(Solution().process())

**邻接矩阵存储为一个二维数组或列表：**

from typing import List
     
     
    class Solution:
        def dijkstra(self, s: int, t: int, n: int, g: List[List[int]]):
            dis = [0] * (n + 1)
            dis[s] = 1
            vis = [0] * (n + 1)
            for i in range(n):
                k = -1
                # 注意这里下标是从1开始的, 如果不注意结果就是错的
                for j in range(1, n + 1):
                    if vis[j] == 0 and (k == -1 or dis[k] < dis[j]):
                        k = j
                vis[k] = 1
                for i in range(1, n + 1):
                    dis[i] = max(dis[i], dis[k] * g[k][i])
            return dis[t]
     
        def process(self):
            n, m = map(int, input().split())
            # 邻接矩阵存储
            g = [[0] * (n + 1) for i in range(n + 1)]
            for i in range(m):
                x, y, z = map(int, input().split())
                c = (100 - z) / 100
                g[x][y] = g[y][x] = max(g[x][y], c)
            s, t = map(int, input().split())
            return "{:.8f}".format(100 / self.dijkstra(s, t, n, g))
     
     
    if __name__ == "__main__":
        print(Solution().process())

[https_www.acwing.com_problem_content_description_1128]: https://www.acwing.com/problem/content/description/1128/