結果

問題 No.2565 はじめてのおつかい
コンテスト
ユーザー Kohei
提出日時 2026-08-23 19:03:58
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 205 ms / 2,000 ms
+ 806µs
コード長 1,060 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 256 ms
コンパイル使用メモリ 95,964 KB
実行使用メモリ 99,628 KB
最終ジャッジ日時 2026-08-23 19:04:12
合計ジャッジ時間 11,906 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = 1e18
from collections import deque
N, M = map(int, input().split())
G = [list() for _ in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)

dist = [INF] * N
dist[0] = 0
que = deque([0])
while que:
    pos = que.popleft()
    for nex in G[pos]:
        if dist[nex] == INF:
            dist[nex] = dist[pos] + 1
            que.append(nex)

dist_from_N = [INF] * N
dist_from_N[-1] = 0
que = deque([N - 1])
while que:
    pos = que.popleft()
    for nex in G[pos]:
        if dist_from_N[nex] == INF:
            dist_from_N[nex] = dist_from_N[pos] + 1
            que.append(nex)

dist_from_N_1 = [INF] * N
dist_from_N_1[-2] = 0
que = deque([N - 2])
while que:
    pos = que.popleft()
    for nex in G[pos]:
        if dist_from_N_1[nex] == INF:
            dist_from_N_1[nex] = dist_from_N_1[pos] + 1
            que.append(nex)

ans1 = dist[-2] + dist_from_N_1[-1] + dist_from_N[0]
ans2 = dist[-1] + dist_from_N[-2] + dist_from_N_1[0]
ans = min(ans1, ans2)
if ans >= INF:
    ans = -1
print(ans)
0