結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
![]() |
提出日時 | 2024-07-04 01:46:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 771 bytes |
コンパイル時間 | 210 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 95,940 KB |
最終ジャッジ日時 | 2024-07-04 01:46:46 |
合計ジャッジ時間 | 13,012 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
from collections import defaultdict, deque INF = 1 << 60 N, M = map(int, input().split()) adj = defaultdict(list) for _ in range(M): u, v = map(lambda x: int(x)-1, input().split()) adj[u].append(v) def calc(src: int) -> list: dists = [INF] * N dists[src] = 0 q = deque([src]) while q: v = q.popleft() for to in adj[v]: if dists[to] <= dists[v] + 1: continue dists[to] = dists[v] + 1 q.append(to) return dists def distance(src, dst) -> int: d = calc(src) return d[dst] d1 = distance(0, N-2) + distance(N-2, N-1) + distance(N-1, 0) d2 = distance(0, N-1) + distance(N-1, N-2) + distance(N-2, 0) if d1 >= INF and d2 >= INF: print(-1) exit() ans = min(d1, d2) print(ans)