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

为了解决这个问题，我们需要找到从A到B的最优转账路径，使得转账后B最终收到100元所需的最小初始金额。这个问题可以通过图论中的最长路径问题来解决，通过反向转换并使用Dijkstra算法来求解。

方法思路

解决代码

import heapqdef main():    import sys    input = sys.stdin.read().split()    idx = 0    n = int(input[idx])    idx += 1    m = int(input[idx])    idx += 1    INF = float('inf')    graph = [[] for _ in range(n + 1)]  # 1-based indexing    for _ in range(m):        x = int(input[idx])        idx += 1        y = int(input[idx])        idx += 1        z = float(input[idx])        idx += 1        rate = 1.0 / ((100 - z) / 100)        graph[x].append((y, rate))        graph[y].append((x, rate))    A = int(input[idx])    idx += 1    B = int(input[idx])    idx += 1    # Dijkstra from B to A    dist = [INF] * (n + 1)    dist[B] = 1.0    heap = []    heapq.heappush(heap, (0, B))    while heap:        current_dist, u = heapq.heappop(heap)        if u == A:            break        if current_dist > dist[u]:            continue        for v, w in graph[u]:            if dist[v] < dist[u] * w:                dist[v] = dist[u] * w                heapq.heappush(heap, (dist[v], v))    total_rate = dist[A]    min_A = 100.0 / total_rate    print("{0:.8f}".format(min_A))if __name__ == "__main__":    main()

代码解释

这个方法通过反向转换和Dijkstra算法高效地解决了问题，确保了找到最优转账路径并计算最小初始金额。

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