結果

問題 No.1065 電柱 / Pole (Easy)
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:11:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 735 ms / 2,000 ms
コード長 1,296 bytes
記録
コンパイル時間 376 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 166,032 KB
最終ジャッジ日時 2025-03-20 21:13:21
合計ジャッジ時間 18,609 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import math
import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    m = int(input[ptr])
    ptr += 1
    x = int(input[ptr])
    ptr += 1
    y = int(input[ptr])
    ptr += 1

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

    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        pj = int(input[ptr])
        ptr += 1
        qj = int(input[ptr])
        ptr += 1
        x1, y1 = coords[pj - 1]
        x2, y2 = coords[qj - 1]
        dx = x1 - x2
        dy = y1 - y2
        dist = math.hypot(dx, dy)
        adj[pj].append((qj, dist))
        adj[qj].append((pj, dist))

    distance = [math.inf] * (n + 1)
    distance[x] = 0.0
    heap = []
    heapq.heappush(heap, (0.0, x))

    while heap:
        current_dist, u = heapq.heappop(heap)
        if u == y:
            break
        if current_dist > distance[u]:
            continue
        for v, w in adj[u]:
            if distance[v] > distance[u] + w:
                distance[v] = distance[u] + w
                heapq.heappush(heap, (distance[v], v))

    print("{0:.9f}".format(distance[y]))

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