結果
問題 |
No.1576 織姫と彦星
|
ユーザー |
|
提出日時 | 2022-03-19 15:40:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 1,001 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 64,936 KB |
最終ジャッジ日時 | 2024-10-04 17:01:26 |
合計ジャッジ時間 | 6,332 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 54 |
ソースコード
#!/usr/bin/env python3 def main(): import math from collections import deque INF = 10 ** 16 def bfs(edges: "List[to]", start_node: int) -> list: q = deque() dist = [INF] * len(edges) q.append(start_node) dist[start_node] = 0 while q: now = q.popleft() for next in edges[now]: if dist[next] != INF: continue q.append(next) dist[next] = dist[now] + 1 return dist N = int(input()) st, ed = map(int, input().split()) stones = [st] + list(map(int, input().split())) + [ed] G = [[] for _ in range(N + 2)] for i in range(N + 1): for j in range(i + 1, N + 2): w = stones[i] ^ stones[j] if w == 0 or math.log2(w).is_integer(): G[i].append(j) G[j].append(i) d = bfs(G, 0) print(d[-1] - 1 if d[-1] != INF else -1) return if __name__ == '__main__': main()