【模板】单源最短路2

[编程题]【模板】单源最短路2

热度指数：16234 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个无向图，图中包含 5000 个点 m 个边，任意两个点之间的距离是 w ，无重边或自环。请求出1号点到n号点的最短距离。

注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.

输入描述:


第一行两个整数n和m，表示图的点和边数。



接下来m行，每行三个整数u，v, w，表示u到v有一条无向边, 长度为w。

输出描述:



输出一行，表示1到n的最短路，如不存在，输出-1.

示例1

输入

输出

示例2

输入

输出

-1

说明

1号点不能到4号点。

算法知识视频讲解

Python3

南肯辛顿男子技校冯师傅

我这用例8怎么过不了鸭, 是哪里的问题啊

import heapq
import sys

n, m = map(int, input().split())

# 使用字典来存储图的邻接表
graph = {}

# 读取输入的边信息
for line in sys.stdin:
    u, v, w = map(int, line.split())

    # 初始化字典键，如果不存在则初始化为空列表
    if u-1 not in graph:
        graph[u-1] = []
    if v-1 not in graph:
        graph[v-1] = []

    # 由于是无向图，双向添加边
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))

# 初始化距离字典，所有节点的初始距离为无穷大
dist = {node: float('inf') for node in graph}
dist[0] = 0  # 起点的距离为0

# 初始化最小堆，开始Dijkstra算法
mini_heap = [(0, 0)]  # (距离, 节点)

while mini_heap:
    current_dist, u = heapq.heappop(mini_heap)
    
    # 如果当前节点的距离已经大于记录的最短距离，跳过
    if current_dist > dist[u]:
        continue
    
    # 更新邻居节点的距离
    for v, weight in graph[u]:
        if dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight
            heapq.heappush(mini_heap, (dist[v], v))

        # # Debug: 打印更新信息
        # print(f"Updated dist[{v}] to {dist[v]} via {u} with edge weight {weight}")

# 输出从节点 1 到 n 的最短距离，如果不可达则返回 -1
if n-1 in dist and dist[n-1] != float('inf'):
    print(dist[n-1])
else:
    print(-1)

发表于 2024-08-16 16:58:48 回复(2)