結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-12-02 15:51:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 252 ms / 2,000 ms |
コード長 | 1,415 bytes |
コンパイル時間 | 381 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 113,544 KB |
最終ジャッジ日時 | 2024-09-26 19:25:13 |
合計ジャッジ時間 | 9,868 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
from collections import defaultdict, deque n, m = map(int, input().split()) graph = defaultdict(set) for i in range(m): a, b = map(lambda x: int(x) - 1, input().split()) graph[a].add(b) INF = float("inf") startdist = [INF for _ in range(n)] startdist[0]=0 startD=deque() startD.append([0,0]) while startD: now, dist = startD.popleft() if startdist[now] < dist: continue for next in graph[now]: if startdist[next] > dist + 1: startdist[next] = dist + 1 startD.append([next, dist + 1]) if startdist[-1]==INF or startdist[-2]==INF: print("-1") exit() INF = float("inf") n1dist = [INF for _ in range(n)] n1dist[-1]=0 n1D=deque() n1D.append([n-1,0]) while n1D: now, dist = n1D.popleft() if n1dist[now] < dist: continue for next in graph[now]: if n1dist[next] > dist + 1: n1dist[next] = dist + 1 n1D.append([next, dist + 1]) INF = float("inf") n2dist = [INF for _ in range(n)] n2dist[-2]=0 n2D=deque() n2D.append([n-2,0]) while n2D: now, dist = n2D.popleft() if n2dist[now] < dist: continue for next in graph[now]: if n2dist[next] > dist + 1: n2dist[next] = dist + 1 n2D.append([next, dist + 1]) ans = INF ans = min(ans, startdist[-1]+n1dist[-2]+n2dist[0]) ans = min(ans, startdist[-2]+n2dist[-1]+n1dist[0]) print(ans if ans!=INF else -1)