結果

問題 No.2565 はじめてのおつかい
ユーザー lloyz
提出日時 2023-12-12 07:28:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 397 ms / 2,000 ms
コード長 706 bytes
コンパイル時間 318 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 101,616 KB
最終ジャッジ日時 2024-09-27 04:47:09
合計ジャッジ時間 14,171 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque

n, m = map(int, input().split())
G = defaultdict(list)
for _ in range(m):
    u, v = map(int, input().split())
    G[u - 1].append(v - 1)

INF = 10**18
DP = [[INF for _ in range(1 << 2)] for _ in range(n)]
DP[0][0] = 0
Que = deque([(0, 0)])
while Que:
    cp, cbit = Que.popleft()
    cc = DP[cp][cbit]
    nc = cc + 1
    for np in G[cp]:
        if np == n - 2:
            nbit = cbit | 1
        elif np == n - 1:
            nbit = cbit | (1 << 1)
        else:
            nbit = cbit
        if nc >= DP[np][nbit]:
            continue
        DP[np][nbit] = nc
        Que.append((np, nbit))
if DP[0][-1] == INF:
    print(-1)
else:
    print(DP[0][-1])
0