結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
👑 |
提出日時 | 2023-09-21 20:18:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 788 bytes |
コンパイル時間 | 192 ms |
コンパイル使用メモリ | 82,208 KB |
実行使用メモリ | 90,240 KB |
最終ジャッジ日時 | 2024-07-07 13:50:14 |
合計ジャッジ時間 | 9,023 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
from collections import deque INF = 1 << 60 N, M = map(int, input().split()) graph = [[] for _ in range(N)] for _ in range(M): u, v = map(int, input().split()) u -= 1; v -= 1 graph[u].append(v) def bfs(start): distances = [INF]*N distances[start] = 0 que = deque([(start, 0)]) while que: now, d = que.popleft() for next in graph[now]: if distances[next] < INF: continue distances[next] = d + 1 que.append((next, d + 1)) return distances dist = { 0: bfs(0), N-2: bfs(N-2), N-1: bfs(N-1) } ans = min( dist[0][N-2] + dist[N-2][N-1] + dist[N-1][0], dist[0][N-1] + dist[N-1][N-2] + dist[N-2][0] ) if ans < INF: print(ans) else: print(-1)