結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 14:35:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 656 ms / 2,000 ms |
コード長 | 648 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 212,864 KB |
最終ジャッジ日時 | 2024-09-26 16:55:08 |
合計ジャッジ時間 | 19,991 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
from collections import deque INF=pow(2,61)-1 N,M=map(int,input().split()) gr=[[set() for i in range(4)] for i in range(N)] for i in range(M): u,v=map(int,input().split()) for j in range(4): if v==N-1: gr[u-1][j].add((v-1,j|1)) elif v==N: gr[u-1][j].add((v-1,j|2)) else: gr[u-1][j].add((v-1,j)) pos=deque([(0,0)]) ans=[[INF]*4 for i in range(N)] ans[0][0]=0 while len(pos)>0: a,b=pos.popleft() for i,j in gr[a][b]: if ans[i][j]>ans[a][b]+1: ans[i][j]=ans[a][b]+1 pos.append((i,j)) if ans[0][3]>=INF: print(-1) else: print(ans[0][3])