【模板】单源最短路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号点。

算法知识视频讲解

Python 3

lq4

import heapq
n, m = map(int,input().strip().split())
graph = [[] for _ in range(5001)]
for _ in range(m):
    u,v,w = map(int,input().strip().split())
    graph[u].append((v,w))
    graph[v].append((u,w))
dist = [float('inf')]*(5001)
dist[1] = 0
pq = [(0,1)]  # heap中排序的顺序是基于元组中第一个元素的，所以距离在前
while pq:
    d, u = heapq.heappop(pq)
    for v,w in graph[u]:
        if dist[u]+w < dist[v]:
            dist[v] = dist[u] + w
            heapq.heappush(pq,(dist[v],v))
print(dist[n] if dist[n]!=float('inf') else -1)

哪个**出的题，示例全是坑，示例2和8报错的需要注意n是目标点而不是点的总数！而u和v又是从1开始的，所以初始化邻接矩阵的时候就定其长度为5001

编辑于 2025-04-08 20:41:06 回复(0)