【模板】单源最短路1

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

热度指数：11371 时间限制：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号点。

算法知识视频讲解

Python3

逃不掉

import collections 

def bfs_sin(start,target,graph):
    dp = collections.deque()
    v = set()
    dp.append(start)
    res = {start:0}
    while dp:
        u = dp.popleft()
        if u == target:
            return res[target]
        for i in graph[u]:
            if i not in v:
                v.add(i)
                res[i] = res[u] + 1
                dp.append(i)
    return '-1'
            
n,m = map(int,input().split())
graph = collections.defaultdict(list)
for i in range(m):
    u,v = map (int,input().split())
    graph[u].append(v)
    graph[v].append(u)
print(bfs_sin(1,n,graph))

发表于 2025-04-19 19:22:52 回复(0)

Python3

HarukiHorizon

import sys
from collections import deque, defaultdict


def bfs_shortest_path(n, m, edges, start, target):
    # 创建邻接表
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # 初始化距离数组
    dist = [-1] * (n + 1)
    dist[start] = 0
    
    # BFS 队列
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if dist[neighbor] == -1:  # 未访问
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
                # 如果找到目标节点，直接返回距离
                if neighbor == target:
                    return dist[target]
    
    # 如果 BFS 结束还未找到目标节点，返回 -1 表示无法到达
    return -1

# 示例用法
f = 5000  # 节点数
n, m = map(int, input().split())

edges = []
# edges = [(1, 2), (2, 3), (1, 3), (3, 4), (4, 5)]  # 示例边
for i in range(m):
    u, v = map(int, input().split())
    edges.append((u,v))

start = 1  # 起点
target = n  # 目标点

print(bfs_shortest_path(f, m, edges, start, target))

GPT给的，挺标准

发表于 2024-12-05 00:28:36 回复(0)

Python3

要冲外企的鲸鱼很想run

大佬们，跟gpt学的，提交后显示第13个测试用例结果错了。但是我没看出问题在哪，有没有人指点一下

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 = input().split()
for line in sys.stdin:
    u,v = line.split()
    edges.append( (int(u), int(v)) )
shortest_path(int(n), edges)

发表于 2024-08-21 20:03:24 回复(3)