题解 | 【模板】单源最短路1

n,m = input().split(" ")
n,m = int(n),int(m)
dl = [input().split(" ") for i in range(m)]

node_root = {}
for d in dl:
    if d[0] in node_root:
        node_root[d[0]].append(d[1])
    else:
        node_root[d[0]] = [d[1]]
    if d[1] in node_root: #防止输入中只有n 1 没有 1 n的描述方式，其实这两种描述的意思是等价。
        node_root[d[1]].append(d[0])
    else:
        node_root[d[1]] = [d[0]]


count = 0
flag=False
vis = [False] * 5001
vis[1] = True
nodes = node_root['1']
while nodes:
    if flag:
        break
    tmp_nodes = []
    for node in nodes:
        if not vis[int(node)] and node in node_root:
            tmp_nodes.extend(node_root[node])
            if str(n) in nodes:
                flag = True
                break
        vis[int(node)] = True

    nodes = list(set(tmp_nodes))
    count+=1

if flag == False:
    print(-1)
else:
    print(count)