結果

問題 No.2565 はじめてのおつかい
ユーザー hiro1729hiro1729
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
54,016 KB
testcase_01 AC 48 ms
54,400 KB
testcase_02 AC 48 ms
53,888 KB
testcase_03 AC 330 ms
102,016 KB
testcase_04 AC 225 ms
102,144 KB
testcase_05 AC 47 ms
54,016 KB
testcase_06 AC 259 ms
83,584 KB
testcase_07 AC 168 ms
79,488 KB
testcase_08 AC 194 ms
81,920 KB
testcase_09 AC 208 ms
81,408 KB
testcase_10 AC 216 ms
82,284 KB
testcase_11 AC 340 ms
91,136 KB
testcase_12 AC 146 ms
78,080 KB
testcase_13 AC 207 ms
81,664 KB
testcase_14 AC 279 ms
86,400 KB
testcase_15 AC 273 ms
85,284 KB
testcase_16 AC 205 ms
92,544 KB
testcase_17 AC 123 ms
78,336 KB
testcase_18 AC 119 ms
80,896 KB
testcase_19 AC 234 ms
88,448 KB
testcase_20 AC 269 ms
87,680 KB
testcase_21 AC 270 ms
88,064 KB
testcase_22 AC 162 ms
83,328 KB
testcase_23 AC 183 ms
83,200 KB
testcase_24 AC 116 ms
77,568 KB
testcase_25 AC 275 ms
88,064 KB
testcase_26 AC 180 ms
82,944 KB
testcase_27 AC 239 ms
88,832 KB
testcase_28 AC 287 ms
88,960 KB
testcase_29 AC 310 ms
92,288 KB
testcase_30 AC 275 ms
89,856 KB
testcase_31 AC 289 ms
88,704 KB
testcase_32 AC 178 ms
82,816 KB
testcase_33 AC 267 ms
89,344 KB
testcase_34 AC 311 ms
86,784 KB
testcase_35 AC 235 ms
91,648 KB
testcase_36 AC 260 ms
89,472 KB
testcase_37 AC 194 ms
83,968 KB
testcase_38 AC 239 ms
86,528 KB
testcase_39 AC 240 ms
85,504 KB
testcase_40 AC 305 ms
92,160 KB
testcase_41 AC 310 ms
92,900 KB
testcase_42 AC 222 ms
83,200 KB
testcase_43 AC 228 ms
85,376 KB
testcase_44 AC 190 ms
81,792 KB
testcase_45 AC 158 ms
80,256 KB
testcase_46 AC 287 ms
85,888 KB
testcase_47 AC 198 ms
80,896 KB
testcase_48 AC 203 ms
81,792 KB
testcase_49 AC 142 ms
77,952 KB
testcase_50 AC 201 ms
81,664 KB
testcase_51 AC 46 ms
53,760 KB
testcase_52 AC 152 ms
79,744 KB
権限があれば一括ダウンロードができます

ソースコード

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