結果

問題 No.1069 電柱 / Pole (Hard)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:45:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,051 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 402,748 KB
最終ジャッジ日時 2025-03-20 20:45:11
合計ジャッジ時間 4,124 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 78
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, M, K = map(int, input[ptr:ptr+3])
    ptr +=3
    X, Y = map(int, input[ptr:ptr+2])
    ptr +=2
    X -= 1  # convert to 0-based index
    Y -= 1

    poles = []
    for _ in range(N):
        x = int(input[ptr])
        y = int(input[ptr+1])
        poles.append((x, y))
        ptr +=2

    # Build adjacency list
    adj = [[] for _ in range(N)]
    for _ in range(M):
        P = int(input[ptr]) - 1
        Q = int(input[ptr+1]) - 1
        ptr +=2
        dx = poles[P][0] - poles[Q][0]
        dy = poles[P][1] - poles[Q][1]
        length = math.hypot(dx, dy)
        adj[P].append((Q, length))
        adj[Q].append((P, length))

    # Priority queue: (current_sum, current_node, visited (frozenset))
    heap = []
    initial_visited = frozenset([X])
    heapq.heappush(heap, (0.0, X, initial_visited))

    all_Y_sums = []
    cutoff = None

    while heap and len(all_Y_sums) < K:
        current_sum, current_u, visited = heapq.heappop(heap)

        if cutoff is not None and current_sum > cutoff:
            break

        if current_u == Y:
            all_Y_sums.append(current_sum)
            if len(all_Y_sums) == K:
                # Update cutoff to current_sum which is the K-th smallest so far
                cutoff = current_sum
            continue

        for v, length in adj[current_u]:
            if v not in visited:
                new_sum = current_sum + length
                new_visited = visited.union(frozenset([v]))

                # Prune paths that exceed the cutoff if it's set
                if cutoff is not None and new_sum > cutoff:
                    continue

                heapq.heappush(heap, (new_sum, v, new_visited))

    # Prepare the output
    while len(all_Y_sums) < K:
        all_Y_sums.append(-1)
    for sum_val in all_Y_sums[:K]:
        if sum_val == -1:
            print(-1)
        else:
            print("{0:.6f}".format(sum_val))

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