結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
![]() |
提出日時 | 2023-12-21 00:25:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 768 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 90,404 KB |
最終ジャッジ日時 | 2024-09-27 10:19:40 |
合計ジャッジ時間 | 10,186 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 19 WA * 31 |
ソースコード
N,M=map(int,input().split()) G=[[] for i in range(N)] for i in range(M): a,b=map(int,input().split()) G[a-1].append(b-1) from collections import deque S=deque() dist=[10**10]*N dist[0]=0 S.append(0) while S: x=S.popleft() for y in G[x]: if dist[y]<10**8: continue dist[y]=dist[x]+1 S.append(y) L1=[10**10]*N L1[N-1]=0 S=deque() S.append(N-1) while S: x=S.popleft() for y in G[x]: if L1[y]<10**8: continue L1[y]=L1[x]+1 S.append(y) L2=[10**10]*N L2[N-2]=0 S=deque() S.append(N-2) while S: x=S.popleft() for y in G[x]: if L2[y]<10**8: continue L2[y]=L2[x]+1 S.append(y) result=10**10 ans=dist[N-1]+L1[N-2]+L2[0] result=min(result,ans) ans=dist[N-2]+L2[N-1]+L1[0] result=min(result,ans) print(result)