結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
|
提出日時 | 2024-06-07 14:17:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 642 bytes |
コンパイル時間 | 154 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 90,368 KB |
最終ジャッジ日時 | 2024-12-25 19:25:29 |
合計ジャッジ時間 | 9,944 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
from collections import deque def bfs(s): dist = [INF] * N dist[s] = 0 que = deque([s]) while que: v = que.popleft() for nv in g[v]: if dist[nv] == INF: dist[nv] = dist[v] + 1 que.append(nv) return dist INF = 1 << 60 N, M = map(int, input().split()) g = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u, v = u - 1, v - 1 g[u].append(v) dist_1 = bfs(0) dist_N = bfs(N - 1) dist_Nm1 = bfs(N - 2) ans = min(dist_1[-1] + dist_N[N - 2] + dist_Nm1[0], dist_1[N - 2] + dist_Nm1[-1] + dist_N[0]) print(ans if ans < INF else -1)