結果

問題 No.2565 はじめてのおつかい
コンテスト
ユーザー hiro1729
提出日時 2024-10-12 12:55:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 340 ms / 2,000 ms
コード長 1,348 bytes
コンパイル時間 824 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 102,144 KB
最終ジャッジ日時 2024-10-12 12:55:43
合計ジャッジ時間 15,566 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict as dd
S = input
R = range
P = print
def I(): return int(S())
def M(): return map(int, S().split())
def L(): return list(M())
def O(): return list(map(int, open(0).read().split()))
def yn(b): print("Yes" if b else "No")
biga = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
smaa = "abcdefghijklmnopqrstuvwxyz"
ctoi = lambda c: ord(c) - ord('a')
itoc = lambda i: chr(ord('a') + i)
inf = 10 ** 18
mod = 998244353
def acc(a):
	b = [0]
	for i in a:
		b.append(b[-1] + i)
	return b

from collections import deque

n,m=M()
g=[[] for _ in R(n)]
g2=[[] for _ in R(n)]
for i in R(m):
	u,v=M()
	u-=1;v-=1
	g[u].append(v);g2[v].append(u)

di=[10**18]*n
di[0]=0
q=deque([0])
while q:
	u=q.popleft()
	for v in g[u]:
		if di[v]>di[u]+1:
			di[v]=di[u]+1
			q.append(v)
di2=[10**18]*n
di2[0]=0
q2=deque([0])
while q2:
	u=q2.popleft()
	for v in g2[u]:
		if di2[v]>di2[u]+1:
			di2[v]=di2[u]+1
			q2.append(v)
di3=[10**18]*n
di3[n-1]=0
q3=deque([n-1])
while q3:
	u=q3.popleft()
	for v in g[u]:
		if di3[v]>di3[u]+1:
			di3[v]=di3[u]+1
			q3.append(v)
di4=[10**18]*n
di4[n-1]=0
q4=deque([n-1])
while q4:
	u=q4.popleft()
	for v in g2[u]:
		if di4[v]>di4[u]+1:
			di4[v]=di4[u]+1
			q4.append(v)
ans=min(di[n-1]+di3[n-2]+di2[n-2],di[n-2]+di4[n-2]+di2[n-1])
if ans>10**9:P(-1)
else:P(ans)
0