题解 | #【模板】单源最短路1# Python3
【模板】单源最短路1
https://www.nowcoder.com/practice/f24504c9ff544f7c808f76693cc34af8
import sys
from collections import defaultdict
import heapq
n, m = list(map(int,input().strip().split(' ')))
adjacent_mat = defaultdict(list)
min_dis = [5001] * (n+1)
not_processed = set()
for i in range(m):
u, v = list(map(int,input().strip().split(' ')))
adjacent_mat[u].append(v)
adjacent_mat[v].append(u)
processed = set()
pq = [] # 记录当前所有从起始点到点i还未确定最短路径的距离以及点i
heapq.heappush(pq,(0,1)) # 起始点为1，距离为0
while len(pq):
cur_dis, cur_pos = heapq.heappop(pq)
processed.add(cur_pos)
if cur_pos == n:
print(cur_dis)
break
for v in adjacent_mat[cur_pos]:
if v in processed: continue
heapq.heappush(pq,(cur_dis+1,v))
else:
print(-1)
海康威视公司福利 1235人发布
这样才显得专业