結果

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

ソースコード

diff # 

import heapq
from math import sqrt

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

    coords = []
    for _ in range(n):
        px = int(input[ptr]); ptr +=1
        py = int(input[ptr]); ptr +=1
        coords.append((px, py))

    adj = [[] for _ in range(n)]
    for _ in range(m):
        p = int(input[ptr])-1; ptr +=1
        q = int(input[ptr])-1; ptr +=1
        dx = coords[p][0] - coords[q][0]
        dy = coords[p][1] - coords[q][1]
        dist = sqrt(dx*dx + dy*dy)
        adj[p].append((q, dist))
        adj[q].append((p, dist))

    heap = []
    visited_states = set()
    initial_visited = frozenset([x])
    heapq.heappush(heap, (0.0, x, initial_visited))

    results = []

    while heap and len(results) < k:
        current_cost, current_node, visited = heapq.heappop(heap)
        state_key = (current_node, visited)
        if state_key in visited_states:
            continue
        visited_states.add(state_key)

        if current_node == y:
            results.append(current_cost)
            continue

        for neighbor, edge_dist in adj[current_node]:
            if neighbor not in visited:
                new_visited = visited.union([neighbor])
                new_cost = current_cost + edge_dist
                new_state = (neighbor, new_visited)
                heapq.heappush(heap, (new_cost, neighbor, 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