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

G国国王想将现有的铁路改造为高速铁路，使得所有城市间可以通过高速铁路到达，并且从所有城市到首都的最短路程与原来的铁路系统一样。为了实现这一目标，我们需要找出最少需要改造的铁路长度。

首先，我们需要分析现有的铁路网络。我们可以使用Dijkstra算法来计算从首都到所有城市的最短路径距离。然后，对于每条铁路，检查它是否在这些最短路径上。如果不在，则需要改造。反之，则可以保留这条铁路。

具体来说，我们可以：

样例分析

在样例输入中，首都是1号城市。计算得到从首都到各城市的最短距离如下：

• 1号到2号：4
• 1号到3号：5
• 1号到4号：7

接下来，检查每条铁路是否在这些最短路径上：

• 1-2（长度4）在1号到2号的最短路径上。
• 1-3（长度5）在1号到3号的最短路径上。
• 2-3（长度2）不在1号到3号的最短路径上，因为1-3的长度5比1-2-3的长度7更短。
• 2-4（长度3）不在1号到4号的最短路径上，因为1-2-4的长度7比1-3-4的长度7更长。
• 3-4（长度2）不在1号到4号的最短路径上，因为1-3-4的长度7比1-2-4的长度7更长。

因此，需要改造的铁路有2-3（长度2）和3-4（长度2），总长度为4。

代码实现

import heapqdef main():    import sys    input = sys.stdin.read    data = input().split()        n = int(data[0])    m = int(data[1])        edges = [[] for _ in range(n)]    index = 2    for _ in range(m):        a = int(data[index])-1        b = int(data[index+1])-1        c = int(data[index+2])        edges[a].append((b, c))        edges[b].append((a, c))        index += 3        def dijkstra(start):        dist = [float('inf')] * n        dist[start] = 0        heap = []        heapq.heappush(heap, (0, start))        visited = [False] * n                while heap:            current_dist, u = heapq.heappop(heap)            if visited[u]:                continue            visited[u] = True            for v, w in edges[u]:                if not visited[v] and dist[v] > dist[u] + w:                    dist[v] = dist[u] + w                    heapq.heappush(heap, (dist[v], v))        return dist        dist_to_capital = dijkstra(0)    dist_from_capital = dijkstra(n-1)        total = 0        for i in range(n):        for j, c in edges[i]:            if dist_to_capital[i] + c == dist_to_capital[j] or dist_from_capital[i] + c == dist_from_capital[j]:                continue            total += c        print(total)if __name__ == "__main__":    main()

代码解释

通过这种方法，我们可以高效地确定最少需要改造的铁路长度，以满足G国国王的要求。

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