本文共 1840 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到一个路径，使得A转账给B后B收到100元的总费用最少。我们可以将这个问题看作是一个图的最短路径问题，但由于涉及百分比扣除，我们需要用一种变形后的最短路径算法来解决。

方法思路

解决代码

import heapq
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    n = int(data[idx])
    idx += 1
    m = int(data[idx])
    idx += 1
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        x = int(data[idx])
        idx += 1
        y = int(data[idx])
        idx += 1
        z = float(data[idx])
        idx += 1
        ratio = 1.0 - z / 100.0
        graph[x].append((y, ratio))
        graph[y].append((x, ratio))
    
    A = int(data[idx])
    idx += 1
    B = int(data[idx])
    idx += 1
    max_ratio = [0.0] * (n + 1)
    max_ratio[A] = 1.0
    heap = []
    heapq.heappush(heap, (-1.0, A))
    while heap:
        current_ratio = -heap[0][0]
        u = heap[0][1]
        if u == B:
            break
        if current_ratio < max_ratio[u]:
            continue
        for v, ratio in graph[u]:
            new_ratio = current_ratio * ratio
            if new_ratio > max_ratio[v]:
                max_ratio[v] = new_ratio
                heapq.heappush(heap, (-new_ratio, v))
    required = 100.0 / (1.0 - max_ratio[B])
    print("{0:.8f}".format(required))
if __name__ == "__main__":
    main()

代码解释

转载地址：http://muug.baihongyu.com/