这个地铁问题一点都不会怎么办

Question

A 市有 n 个交通枢纽，其中 1 号和 n 号非常重要，为了加强运输能力，A 市决定在 1 号到 n 号枢纽间修建一条地铁。 地铁由很多段隧道组成，每段隧道连接两个交通枢纽。经过勘探，有 m 段隧道作为候选，两个交通枢纽之间最多只有一条候选的隧道，没有隧道两端连接着同一个交通枢纽。 现在有 n 家隧道施工的公司，每段候选的隧道只能由一个公司施工，每家公司施工需要的天数一致。而每家公司最多只能修建一条候选隧道。所有公司同时开始施工。 作为项目负责人，你获得了候选隧道的信息，现在你可以按自己的想法选择一部分隧道进行施工，请问修建整条地铁最少需要多少天。 输入格式 输入的第一行包含两个整数 n, m，用一个空格分隔，分别表示交通枢纽的数量和候选隧道的数量。 第 2 行到第 m+1 行，每行包含三个整数 a, b, c，表示枢纽 a 和枢纽 b 之间可以修建一条隧道，需要的时间为 c 天。 输出格式：输出一个整数，为修建整条地铁线路最少需要的天数。样例输入6 61 2 42 3 43 6 71 4 24 5 55 6 6样例输出6样例说明　　可以修建的线路有两种。　　第一种经过的枢纽依次为1, 2, 3, 6，所需要的时间分别是4, 4, 7，则整条地铁线需要7天修完；　　第二种经过的枢纽依次为1, 4, 5, 6，所需要的时间分别是2, 5, 6，则整条地铁线需要6天修完。　　第二种方案所用的天数更少。扩展要求：在完成输出最少需的天数的基础上，输出所经过的枢纽。

Answer 1

这是一道最短路问题，可以使用 Dijkstra 算法或 Floyd 算法求解。下面给出 Dijkstra 算法的示例代码：

from heapq import heappush, heappop

INF = 0x7fffffff

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

dist = [INF] * n
visited = [False] * n
heap = [(0, 0)] # (距离, 节点)

while heap:
    d, u = heappop(heap)
    if visited[u]:
        continue
    visited[u] = True
    dist[u] = d
    for v, w in edges[u]:
        if not visited[v]:
            heappush(heap, (d + w, v))

print(dist[n-1])

这段代码首先读入 n 和 m，然后按照题目所给的边信息构造出一个邻接表 edges。然后，我们用 dist 数组来记录源点到每个节点的最短路径长度，visited 数组来标记每个节点是否已经被访问过，heap 数组作为小根堆维护当前还未确定最短路径的节点。

初始时，将源点加入小根堆中，并将源点的距离设为 0。然后按照 Dijkstra 算法的步骤，每次从小根堆中取出距离最小的节点，更新与它相邻的节点的距离，并将这些节点加入小根堆中。直到小根堆为空或者终点被访问过为止。

最后输出 dist[n-1] 即可得到源点到终点的最短路径长度。

如果需要输出所经过的枢纽，则需要在更新距离时，额外记录下该节点是由哪个节点更新而来，最后通过回溯，即可得到一条最短路径。具体实现可以参考下面的代码：

from heapq import heappush, heappop

INF = 0x7fffffff

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, c))
    edges[b].append((a, c))

dist = [INF] * n
prev = [-1] * n # 记录前驱节点
visited = [False] * n
heap = [(0, 0)] # (距离, 节点)

while heap:
    d, u = heappop(heap)
    if visited[u]:
        continue
    visited[u] = True
    dist[u] = d
    for v, w in edges[u]:
        if not visited[v]:
            heappush(heap, (d + w, v))
            prev[v] = u

if prev[n-1] == -1:
    print("无法到达终点")
else:
    path, u = [n], n-1
    while prev[u] != -1:
        path.append(prev[u]+1)
        u = prev[u]
    path.append(1)
    print(dist[n-1])
    print(" -> ".join(map(str, reversed(path))))

这段代码跟前面的代码类似，只是新增了一个 prev 数组，用来记录每个节点的前驱节点。在更新 dist 数组时，同时更新 prev 数组。最后，通过回溯 prev 数组，就可以得到一条从源点到终点的最短路径。