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

为了解决这个问题，我们需要找到从城市C1到城市C2的最短路径数量以及这条路径上所能聚集的救援队伍数量的最大值。我们将使用优化后的Dijkstra算法来实现这一点。

方法思路

解决代码

import heapq
def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1
    st = int(input[idx])
    idx += 1
    ed = int(input[idx])
    idx += 1
    # 芝加利亚优先队列
    # keys is (distance, city)
    h = []
    INF = float('inf')
    
    weight = [0] * n
    for i in range(n):
        weight[i] = int(input[idx])
        idx += 1
    # 初始化邻接矩阵
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a = int(input[idx])
        idx += 1
        b = int(input[idx])
        idx += 1
        l = int(input[idx])
        idx += 1
        adj[a].append((b, l))
        adj[b].append((a, l))
    # 初始化距离、路径数、权重大数组
    d = [INF] * n
    num = [0] * n
    w = [0] * n
    # 起点处理
    d[st] = 0
    num[st] = 1
    w[st] = weight[st]
    heapq.heappush(h, (0, st))
    while h:
        current_d, u = heapq.heappop(h)
        if current_d > d[u]:
            continue
        # 遍历u的所有邻居
        for (v, l) in adj[u]:
            new_d = current_d + l
            # 判断是否是新的更优路径
            if new_d < d[v]:
                d[v] = new_d
                num[v] = num[u]
                w[v] = w[u] + weight[v]
                heapq.heappush(h, (new_d, v))
            elif new_d == d[v]:
                # 权重的比较
                if (w[u] + weight[v]) > w[v]:
                    # 新路径权重更大，更新w，并增加路径数
                    w[v] = w[u] + weight[v]
                    num[v] += num[u]
                    heapq.heappush(h, (new_d, v))
    print(num[ed], w[ed])
if __name__ == "__main__":
    main()

代码解释

通过这种方法，我们可以高效地解决问题，得到需要的结果。