結果

問題 No.1576 織姫と彦星
ユーザー lam6er
提出日時 2025-03-26 15:45:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 63 ms / 2,000 ms
コード長 1,544 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 64,000 KB
最終ジャッジ日時 2025-03-26 15:45:57
合計ジャッジ時間 4,971 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    n = int(input())
    start, end = map(int, input().split())
    stones = list(map(int, input().split()))
    
    # Nodes: [start, end, stone1, stone2, ...]
    nodes = [start, end] + stones
    m = len(nodes)  # Total nodes: n + 2
    
    # Build adjacency list
    adj = [[] for _ in range(m)]
    for i in range(m):
        for j in range(i + 1, m):
            x = nodes[i]
            y = nodes[j]
            z = x ^ y
            if z == 0:
                adj[i].append(j)
                adj[j].append(i)
            else:
                if (z & (z - 1)) == 0:
                    adj[i].append(j)
                    adj[j].append(i)
    
    # Dijkstra's algorithm to find minimal stone types
    INF = float('inf')
    cost = [INF] * m
    cost[0] = 0  # start node is at index 0
    
    heap = []
    heapq.heappush(heap, (0, 0))
    
    found = False
    while heap:
        current_cost, u = heapq.heappop(heap)
        if u == 1:  # end node is at index 1
            print(current_cost)
            found = True
            break
        if current_cost > cost[u]:
            continue
        for v in adj[u]:
            # Check if the node is a stone (index >= 2)
            if v >= 2:
                new_cost = current_cost + 1
            else:
                new_cost = current_cost
            if new_cost < cost[v]:
                cost[v] = new_cost
                heapq.heappush(heap, (new_cost, v))
    
    if not found:
        print(-1)

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