結果

問題 No.1069 電柱 / Pole (Hard)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:33:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,929 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 81,680 KB
実行使用メモリ 304,596 KB
最終ジャッジ日時 2025-06-12 21:34:42
合計ジャッジ時間 4,237 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 78
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr += 1
    M = int(data[ptr])
    ptr += 1
    K = int(data[ptr])
    ptr += 1
    X = int(data[ptr]) - 1
    ptr += 1
    Y = int(data[ptr]) - 1
    ptr += 1

    coords = []
    for _ in range(N):
        p = int(data[ptr])
        ptr += 1
        q = int(data[ptr])
        ptr += 1
        coords.append((p, q))

    edges = [[] for _ in range(N)]
    for _ in range(M):
        P = int(data[ptr]) - 1
        ptr += 1
        Q = int(data[ptr]) - 1
        ptr += 1
        dx = coords[P][0] - coords[Q][0]
        dy = coords[P][1] - coords[Q][1]
        dist = (dx**2 + dy**2) ** 0.5
        edges[P].append((Q, dist))
        edges[Q].append((P, dist))

    heap = []
    visited = dict()
    initial_visited = 1 << X
    heapq.heappush(heap, (0.0, X, initial_visited))
    visited_key = (X, initial_visited)
    visited[visited_key] = 0.0

    results = []
    while heap:
        current_dist, u, visited_bits = heapq.heappop(heap)
        if u == Y:
            results.append(current_dist)
            if len(results) == K:
                break
        visited_key = (u, visited_bits)
        if visited.get(visited_key, float('inf')) < current_dist:
            continue
        for v, dist in edges[u]:
            if not (visited_bits & (1 << v)):
                new_dist = current_dist + dist
                new_visited = visited_bits | (1 << v)
                key_new = (v, new_visited)
                if key_new not in visited or new_dist < visited.get(key_new, float('inf')):
                    visited[key_new] = new_dist
                    heapq.heappush(heap, (new_dist, v, new_visited))

    for i in range(K):
        if i < len(results):
            print("{0:.6f}".format(results[i]))
        else:
            print(-1)

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