本文共 1796 字，大约阅读时间需要 5 分钟。
为了解决这个问题，我们需要找到一个路径，使得A转账给B后B收到100元的总费用最少。我们可以将这个问题看作是一个图的最短路径问题，但由于涉及百分比扣除，我们需要用一种变形后的最短路径算法来解决。
问题分析：我们需要计算从A转到B的最优路径，使得在扣除手续费后B收到100元。每次转账都会扣除一定的百分比手续费，因此我们需要找到使总扣除费率最大的路径。
转换问题：将每次转账的百分比手续费转换为保留比例，然后将问题转化为寻找从A到B的最大扣除费率路径。这样，总费用最少的路径就是使得保留比例最大的路径。
算法选择：使用优先队列（大顶堆）来实现一种变形后的Dijkstra算法。我们记录从A到每个节点的最大扣除费率，并不断更新邻居节点的最大扣除费率。
实现步骤：
import heapqdef 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() sys.stdin.read读取所有输入数据，并将其拆分为列表处理。max_ratio数组记录从A到每个节点的最大扣除费率，优先队列用于处理节点，按当前最大保留比例排序。转载地址：http://muug.baihongyu.com/