結果
問題 |
No.1576 織姫と彦星
|
ユーザー |
|
提出日時 | 2025-02-27 14:43:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 670 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 76,876 KB |
最終ジャッジ日時 | 2025-02-27 14:44:03 |
合計ジャッジ時間 | 10,033 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 54 |
ソースコード
from collections import deque N = int(input()) A = [0]*(N+2) a,b = map(int,input().split()) A[0] = a A[N+1] = b A[1:N+1] = map(int,input().split()) def dh(x,y): cnt = 0 for k in range(30+1): if (x>>k)&1!=(y>>k)&1: cnt += 1 return cnt G = {i:[] for i in range(N+2)} for i in range(N+1): for j in range(i+1,N+2): if dh(A[i],A[j])<=1: G[i].append(j) G[j].append(i) dist = [-1]*(N+2) dist[0] = 0 que = deque([0]) while que: x = que.popleft() for y in G[x]: if dist[y]==-1: dist[y] = dist[x]+1 que.append(y) if dist[N+1]<0: print(-1) else: print(dist[N+1]-1)