結果

問題 No.2565 はじめてのおつかい
ユーザー Lucagon
提出日時 2023-12-02 16:48:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 261 ms / 2,000 ms
コード長 933 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 93,660 KB
最終ジャッジ日時 2024-09-26 20:44:52
合計ジャッジ時間 11,563 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict,deque

n,m = map(int,input().split())
g = defaultdict(list)

for i in range(m):
    u,v = map(int,input().split())
    g[u].append(v)

dist1 = [-1]*(n+1)
que = deque([1])
dist1[1] = 0
while que:
    q = que.popleft()
    for i in g[q]:
        if dist1[i] == -1:
            dist1[i] = dist1[q] + 1
            que.append(i)

dist2 = [-1]*(n+1)
que = deque([n-1])
dist2[n-1] = 0
while que:
    q = que.popleft()
    for i in g[q]:
        if dist2[i] == -1:
            dist2[i] = dist2[q] + 1
            que.append(i)

dist3 = [-1]*(n+1)
que = deque([n])
dist3[n] = 0
while que:
    q = que.popleft()
    for i in g[q]:
        if dist3[i] == -1:
            dist3[i] = dist3[q] + 1
            que.append(i)

if -1 in [dist1[n],dist3[n-1],dist2[1]] or -1 in [dist1[n-1],dist2[n],dist3[1]]:
    print(-1)
    exit()

print(min(dist1[n] + dist3[n-1] + dist2[1], dist1[n-1] + dist2[n] + dist3[1]))
0