AcWing 847. 图中点的层次-python
原题链接
简单
作者:
四舍五入
,
2022-02-22 12:28:35
,
所有人可见
,
阅读 120
python 代码
from collections import deque
N = 100010
def add(a,b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def bfs():
while q:
t = q.popleft()
i = h[t]
while i != -1:
j = e[i]
if d[j] == -1:
d[j] = d[t] + 1
q.append(j)
i = ne[i]
return d[n]
if __name__ == '__main__':
h, e, ne, idx = [-1]*N, [0]*N, [0]*N, 0
d = [-1]*N
q = deque()
q.append(1)
d[1] = 0
n, m = map(int, input().split())
for i in range(m):
a,b = map(int, input().split())
add(a,b)
print(bfs())