結果

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

ソースコード

diff # 

import math
import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    M = int(input[ptr+1])
    K = int(input[ptr+2])
    ptr +=3
    X = int(input[ptr])-1
    Y = int(input[ptr+1])-1
    ptr +=2
    coords = []
    for _ in range(N):
        x = int(input[ptr])
        y = int(input[ptr+1])
        coords.append((x,y))
        ptr +=2
    edges = [[] for _ in range(N)]
    edge_list = []
    for _ in range(M):
        u = int(input[ptr])-1
        v = int(input[ptr+1])-1
        ptr +=2
        dx = coords[u][0] - coords[v][0]
        dy = coords[u][1] - coords[v][1]
        dist = math.hypot(dx, dy)
        edges[u].append((v, len(edge_list), dist))
        edges[v].append((u, len(edge_list), dist))
        edge_list.append((u, v))
    
    heap = []
    visited = dict()
    initial_used = 0
    heapq.heappush(heap, (0.0, X, initial_used))
    visited[(X, initial_used)] = 0.0
    ans = []
    while heap and len(ans) < K:
        current_dist, u, used_mask = heapq.heappop(heap)
        if u == Y:
            ans.append(current_dist)
            if len(ans) >= K:
                break
            continue
        if visited.get((u, used_mask), -1) < current_dist:
            continue
        for v, e_idx, dist in edges[u]:
            if (used_mask & (1 << e_idx)) != 0:
                continue
            new_used = used_mask | (1 << e_idx)
            new_dist = current_dist + dist
            if (v, new_used) not in visited or new_dist < visited[(v, new_used)]:
                visited[(v, new_used)] = new_dist
                heapq.heappush(heap, (new_dist, v, new_used))
    
    for _ in range(K):
        if _ < len(ans):
            print("{0:.6f}".format(ans[_]))
        else:
            print(-1)
    print()
    
if __name__ == "__main__":
    main()
0