Python 最快到达医院的方法

摘要：import heapqdef dijkstra(n, edges, start, end):# 构建邻接表graph = [ for _ in range(n + 1)]for u, v, w in edges:graph[u].append((v, w))

import heapqdef dijkstra(n, edges, start, end):# 构建邻接表graph = [ for _ in range(n + 1)]for u, v, w in edges:graph[u].append((v, w))graph[v].append((u, w)) # 如果是无向图，需要添加双向边# 初始化距离数组dist = [float('inf')] * (n + 1)dist[start] = 0# 使用优先队列（堆）heap = [(0, start)]while heap:current_dist, u = heapq.heappop(heap)# 如果当前节点的距离已经更新过，跳过if current_dist > dist[u]:continue# 遍历邻居节点for v, w in graph[u]:if dist[v] > dist[u] + w:dist[v] = dist[u] + wheapq.heappush(heap, (dist[v], v))# 返回起点到终点的最短距离return dist[end]# 输入处理def main:# 读取节点数和道路数n, m = map(int, input.split)# 读取道路信息edges = for _ in range(m):u, v, w = map(int, input.split)edges.append((u, v, w))# 读取起点和终点s, t = map(int, input.split)# 调用 Dijkstra 算法result = dijkstra(n, edges, s, t)print(result)# 运行主函数if __name__ == "__main__":main问题分析：

这是一个典型的单源最短路径问题，可以使用 Dijkstra 算法解决。

Dijkstra 算法适用于加权图中的最短路径问题，且权重（通行时间）必须为非负数。

算法选择：

使用 Dijkstra 算法，通过优先队列（堆）实现，以提高效率。

实现步骤：

构建图的邻接表表示。

使用 Dijkstra 算法计算从起点到所有节点的最短路径。

输出起点到医院节点的最短路径值。