結果

問題 No.1069 電柱 / Pole (Hard)
ユーザー gew1fw
提出日時 2025-06-12 16:42:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,667 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 431,936 KB
最終ジャッジ日時 2025-06-12 16:42:35
合計ジャッジ時間 4,468 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 78
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import heapq
from collections import defaultdict

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

    X = int(input[ptr])-1
    ptr +=1
    Y = int(input[ptr])-1
    ptr +=1

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

    edges = defaultdict(list)
    for _ in range(M):
        P = int(input[ptr])-1
        ptr +=1
        Q = int(input[ptr])-1
        ptr +=1
        dx = points[P][0] - points[Q][0]
        dy = points[P][1] - points[Q][1]
        dist = math.hypot(dx, dy)
        edges[P].append( (Q, dist) )
        edges[Q].append( (P, dist) )

    heap = []
    visited = set()
    heapq.heappush(heap, (0.0, X, frozenset([X])) )
    results = []
    found = 0

    while heap and found < K:
        dist, u, path = heapq.heappop(heap)
        if u == Y:
            if (dist, path) not in visited:
                results.append(dist)
                visited.add( (dist, path) )
                found +=1
            continue
        for v, d in edges[u]:
            if v not in path:
                new_path = set(path)
                new_path.add(v)
                new_path_frozen = frozenset(new_path)
                new_dist = dist + d
                heapq.heappush(heap, (new_dist, v, new_path_frozen) )

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

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