結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 16:12:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 1,616 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 100,864 KB |
最終ジャッジ日時 | 2024-09-26 19:58:39 |
合計ジャッジ時間 | 12,003 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
class Input_kyopro: def II(self): return int(input()) def MI(self): return map(int,input().split()) def MS(self): return map(str,input().split()) def LMI(self): return list(self.MI()) def LMS(self): return list(self.MS()) def LLI(self,N): return [self.LMI() for _ in range(N)] def LLS(self,N): return [self.LMS() for _ in range(N)] def LS(self,N): return [input() for _ in range(N)] def LSL(self,N): return [list(input()) for _ in range(N)] def LI(self,N): return [self.II() for _ in range(N)] I=Input_kyopro() #入力 from collections import deque N,M=I.MI() uv=I.LLI(M) G=[[] for _ in range(N)] for u,v in uv: u-=1 v-=1 G[u].append(v) q=deque() q.append(0) dist=[-1]*N dist[0]=0 while q: pos=q.popleft() for nex in G[pos]: if dist[nex]!=-1: continue dist[nex]=dist[pos]+1 q.append(nex) q=deque() q.append(N-1) dist1=[-1]*N dist1[N-1]=0 while q: pos=q.popleft() for nex in G[pos]: if dist1[nex]!=-1: continue dist1[nex]=dist1[pos]+1 q.append(nex) q=deque() q.append(N-2) dist2=[-1]*N dist2[N-2]=0 while q: pos=q.popleft() for nex in G[pos]: if dist2[nex]!=-1: continue dist2[nex]=dist2[pos]+1 q.append(nex) ans=float('inf') if dist[-1]==-1 or dist[-2]==-1: print(-1) else: if dist1[N-2]!=-1 and dist2[0]!=-1: ans=min(ans,dist[N-1]+dist1[N-2]+dist2[0]) if dist2[N-1]!=-1 and dist1[0]!=-1: ans=min(ans,dist[N-2]+dist2[N-1]+dist1[0]) if ans==float('inf'): print(-1) else: print(ans)