【模板】单源最短路1

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

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

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

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

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

输入描述:

第一行两个整数n和m，表示图的点和边数。
接下来m行，每行两个整数u，v，表示u到v有一条无向边。

输出描述:

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

示例1

输入

输出

示例2

输入

输出

-1

说明

1号点不能到4号点。

算法知识视频讲解

Python

冷飒5611

from collections import deque, defaultdict
import sys
def shortest_path(n, edges):
    graph = defaultdict(list)
    for u,v in edges:
        graph[u].append(v)
        graph[v].append(u)
    queue = deque([1])
    distances = {1:0}
    while queue:
        cur = queue.popleft()
        for neighbor in graph[cur]:
            if neighbor not in distances:
                distances[neighbor] = distances[cur] + 1
                queue.append(neighbor)
            if neighbor == n:
                print(distances[neighbor])
                return
    print(-1)
edges = []
n,m = map(int,input().split())
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
shortest_path(int(n), edges)

发表于 2025-07-29 11:14:03 回复(0)