結果
問題 |
No.1576 織姫と彦星
|
ユーザー |
|
提出日時 | 2022-10-29 17:42:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 131 ms / 2,000 ms |
コード長 | 804 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 82,392 KB |
実行使用メモリ | 76,416 KB |
最終ジャッジ日時 | 2024-07-06 15:23:44 |
合計ジャッジ時間 | 7,126 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 54 |
ソースコード
import sys readline = sys.stdin.readline N = int(readline()) s,g = map(int,readline().split()) A = [s] + list(map(int,readline().split())) + [g] N += 2 def can_connect(X, Y): diff = 0 while X or Y: if (X & 1) ^ (Y & 1): diff += 1 if diff == 2: return False X >>= 1 Y >>= 1 return True G = [[] for i in range(N)] for i in range(N - 1): for j in range(i + 1, N): if can_connect(A[i], A[j]): G[i].append(j) G[j].append(i) visited = [False] * N from collections import deque q = deque([]) q.append([0, 0]) while q: v, cost = q.popleft() if visited[v]: continue visited[v] = True if v == N - 1: print(cost - 1) break for child in G[v]: if visited[child]: continue q.append([child, cost + 1]) else: print(-1)