結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:24:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 250 ms / 2,000 ms |
コード長 | 1,865 bytes |
コンパイル時間 | 435 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 90,240 KB |
最終ジャッジ日時 | 2024-09-26 20:15:19 |
合計ジャッジ時間 | 11,055 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
from collections import deque n, m = map(int, input().split()) g = [[] for _ in range(n)] for i in range(m): u, v = map(lambda x: x-1, map(int, input().split())) g[u].append(v) q = deque([0]) dist = [-1]*n dist[0] = 0 while q: v = q.popleft() for v2 in g[v]: if dist[v2]!=-1: continue dist[v2] = dist[v] + 1 q.append(v2) if dist[n-2]==-1 and dist[n-1]==-1: exit(print(-1)) # 町nから q = deque([n-1]) dist2 = [-1]*n dist2[n-1] = 0 while q: v = q.popleft() for v2 in g[v]: if dist2[v2]!=-1: continue dist2[v2] = dist2[v] + 1 q.append(v2) # 町n-1から q = deque([n-2]) dist3 = [-1]*n dist3[n-2] = 0 while q: v = q.popleft() for v2 in g[v]: if dist3[v2]!=-1: continue dist3[v2] = dist3[v] + 1 q.append(v2) ans = 10**18 if dist[n-2]!=-1 and dist[n-1]==-1: if dist3[n-1]!=-1 and dist2[0]!=-1: ans = min(ans, dist[n-2] + dist3[n-1] + dist2[0]) if dist3[n-1]!=-1 and dist2[n-2]!=-1 and dist3[0]!=-1: ans = min(ans, dist[n-2]+dist3[n-1]+dist2[n-2]+dist3[0]) elif dist[n-2]==-1 and dist[n-1]!=-1: if dist2[n-2]!=-1 and dist3[0]!=-1: ans = min(ans, dist[n-1]+dist2[n-2]+dist3[0]) if dist2[n-2]!=-1 and dist3[n-1]!=-1 and dist2[0]!=-1: ans = min(ans, dist[n-1]+dist2[n-2]+dist3[n-1]+dist2[0]) else: if dist3[n-1]!=-1 and dist2[0]!=-1: ans = min(ans, dist[n-2] + dist3[n-1] + dist2[0]) if dist3[n-1]!=-1 and dist2[n-2]!=-1 and dist3[0]!=-1: ans = min(ans, dist[n-2]+dist3[n-1]+dist2[n-2]+dist3[0]) if dist2[n-2]!=-1 and dist3[0]!=-1: ans = min(ans, dist[n-1]+dist2[n-2]+dist3[0]) if dist2[n-2]!=-1 and dist3[n-1]!=-1 and dist2[0]!=-1: ans = min(ans, dist[n-1]+dist2[n-2]+dist3[n-1]+dist2[0]) if ans==10**18: print(-1) else: print(ans)