結果

問題 No.1069 電柱 / Pole (Hard)
ユーザー lam6er
提出日時 2025-03-31 17:48:57
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,817 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,624 KB
実行使用メモリ 277,664 KB
最終ジャッジ日時 2025-03-31 17:50:13
合計ジャッジ時間 4,021 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 78
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N, M, K = map(int, data[ptr:ptr+3])
    ptr +=3
    X, Y = map(int, data[ptr:ptr+2])
    ptr +=2
    coords = []
    for _ in range(N):
        x, y = map(int, data[ptr:ptr+2])
        coords.append((x, y))
        ptr +=2
    adj = [[] for _ in range(N + 1)]  # 1-based
    for _ in range(M):
        P, Q = map(int, data[ptr:ptr+2])
        ptr +=2
        # Compute distance between P and Q
        x1, y1 = coords[P - 1]
        x2, y2 = coords[Q - 1]
        dx = x1 - x2
        dy = y1 - y2
        distance = (dx*dx + dy*dy)**0.5
        adj[P].append((Q, distance))
        adj[Q].append((P, distance))
    
    start = X
    target = Y
    
    heap = []
    visited = defaultdict(set)
    initial_mask = 1 << (start - 1)  # 1-based to 0-based bitmask
    heapq.heappush(heap, (0.0, start, initial_mask))
    
    answers = []
    
    while heap and len(answers) < K:
        current_len, u, mask = heapq.heappop(heap)
        
        if u == target:
            answers.append(current_len)
            continue
        
        if mask in visited[u]:
            continue
        visited[u].add(mask)
        
        for v, weight in adj[u]:
            if not (mask & (1 << (v - 1))):  # Check if v is not visited
                new_mask = mask | (1 << (v - 1))
                new_len = current_len + weight
                heapq.heappush(heap, (new_len, v, new_mask))
    
    # Fill the remaining answers with -1 if necessary
    while len(answers) < K:
        answers.append(-1)
    
    for ans in answers:
        if ans == -1:
            print(-1)
        else:
            print("{0:.6f}".format(ans))
    
if __name__ == '__main__':
    main()
0