結果

問題 No.1069 電柱 / Pole (Hard)
ユーザー lam6er
提出日時 2025-04-15 21:48:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,038 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 54,096 KB
最終ジャッジ日時 2025-04-15 21:50:20
合計ジャッジ時間 3,988 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 78
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import bisect
import math

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])
    Y = int(input[ptr+1])
    ptr += 2
    coords = []
    for _ in range(N):
        p = int(input[ptr])
        q = int(input[ptr+1])
        coords.append((p, q))
        ptr += 2
    # Build adjacency list
    adj = [[] for _ in range(N + 1)]  # 1-based indexing
    for _ in range(M):
        P = int(input[ptr])
        Q = int(input[ptr+1])
        ptr += 2
        dx = coords[P-1][0] - coords[Q-1][0]
        dy = coords[P-1][1] - coords[Q-1][1]
        dist = math.hypot(dx, dy)
        adj[P].append((Q, dist))
        adj[Q].append((P, dist))
    
    # Priority queue: (current_sum, current_node, visited_tuple)
    heap = []
    initial_visited = tuple(sorted([X]))
    heapq.heappush(heap, (0.0, X, initial_visited))
    
    result = []
    
    while heap and len(result) < K:
        current_sum, current_node, visited = heapq.heappop(heap)
        
        if current_node == Y:
            result.append(current_sum)
            continue
        
        # Generate neighbors
        for (neighbor, dist) in adj[current_node]:
            # Check if neighbor is in visited using binary search
            idx = bisect.bisect_left(visited, neighbor)
            if idx < len(visited) and visited[idx] == neighbor:
                continue  # already visited
            
            # Create new visited tuple
            new_visited = list(visited)
            new_visited.insert(idx, neighbor)
            new_visited = tuple(new_visited)
            
            new_sum = current_sum + dist
            
            heapq.heappush(heap, (new_sum, neighbor, new_visited))
    
    # Output the results with padding
    for i in range(K):
        if i < len(result):
            print("{0:.6f}".format(result[i]))
        else:
            print(-1)

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