Submission #58981280

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a].append(b)
dist = [float('inf')] * N 
ans = float('inf')
#dist[0] = 1
from heapq import *
que = []
heappush(que,(0,0))
while que:
  di,v = heappop(que)
  for vv in G[v]:
    if vv == 0:
      ans = min(ans, di + 1)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a].append(b)

dist = [float('inf')] * N 
ans = float('inf')
#dist[0] = 1

from heapq import *

que = []
heappush(que,(0,0))

while que:
  di,v = heappop(que)
  for vv in G[v]:
    if vv == 0:
      ans = min(ans, di + 1)
    if dist[vv] > di + 1:
      dist[vv] = di + 1
      heappush(que,(di+1,vv))

print(-1 if ans == float('inf') else ans)

Submission Info

Judge Result