結果

問題 No.1577 織姫と彦星2
ユーザー lam6er
提出日時 2025-03-20 20:48:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 397 ms / 2,000 ms
コード長 2,065 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 99,416 KB
最終ジャッジ日時 2025-03-20 20:48:45
合計ジャッジ時間 13,709 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    start = int(input[idx])
    end = int(input[idx + 1]); idx += 2
    stones = list(map(int, input[idx:idx + N]))
    idx += N

    # Check direct connection between start and end
    def hamming(x, y):
        return bin(x ^ y).count('1')

    if hamming(start, end) <= 1:
        print(0)
        return

    stone_set = set(stones)

    # Check if any single stone can connect start and end
    for s in stones:
        if hamming(start, s) <= 1 and hamming(s, end) <= 1:
            print(1)
            return

    # Build adjacency list for all nodes (start, end, stones)
    adj = {}
    nodes = [start, end] + stones

    def get_neighbors(x):
        neighbors = set()
        neighbors.add(x)
        for i in range(32):
            neighbors.add(x ^ (1 << i))
        valid = []
        for y in neighbors:
            if y == start or y == end:
                valid.append(y)
            elif y in stone_set:
                valid.append(y)
        return valid

    for x in nodes:
        adj[x] = get_neighbors(x)

    # Dijkstra's algorithm
    INF = float('inf')
    dist = {x: INF for x in nodes}
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    found = False
    while heap:
        current_cost, u = heapq.heappop(heap)
        if u == end:
            print(current_cost)
            found = True
            break
        if current_cost > dist[u]:
            continue
        for v in adj[u]:
            if v == start or v == end:
                new_cost = current_cost
            else:
                # v is a stone
                if u in stone_set and u == v:
                    new_cost = current_cost
                else:
                    new_cost = current_cost + 1
            if new_cost < dist.get(v, INF):
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))

    if not found:
        print(-1)

if __name__ == '__main__':
    main()
0