結果
問題 |
No.1576 織姫と彦星
|
ユーザー |
![]() |
提出日時 | 2023-11-01 09:37:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,057 ms / 2,000 ms |
コード長 | 875 bytes |
コンパイル時間 | 274 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 77,696 KB |
最終ジャッジ日時 | 2024-09-25 17:51:43 |
合計ジャッジ時間 | 26,197 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 54 |
ソースコード
N = int(input()) s,e = map(int,input().split()) S = [s] + list(map(int,input().split())) + [e] N += 2 def check(X, Y): L = len(bin(max(X,Y))[2:]) X = bin(X)[2:].zfill(L) Y = bin(Y)[2:].zfill(L) cnt = 0 for i in range(L): if X[i] != Y[i]: cnt += 1 if cnt > 1: return False return True G = [[] for i in range(N)] for i in range(N - 1): for j in range(i + 1, N): if check(S[i], S[j]): G[i].append(j) G[j].append(i) from collections import deque q = deque([]) q.append([0, 0]) visited = [False] * N visited[0] = True while q: v, c = q.popleft() if v == N - 1: print(c - 1) break for child in G[v]: if visited[child]: continue visited[child] = True q.append([child, c + 1]) else: print(-1)