結果

問題 No.1065 電柱 / Pole (Easy)
コンテスト
ユーザー LyricalMaestro
提出日時 2026-05-12 01:54:55
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 680 ms / 2,000 ms
コード長 1,217 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 136 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 138,672 KB
最終ジャッジ日時 2026-05-12 01:55:18
合計ジャッジ時間 19,919 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/1065

import heapq
import math



def main():
    N, M = map(int, input().split())
    X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    pq = []
    for _ in range(N):
        p, q = map(int, input().split())
        pq.append((p, q))
    
    next_nodes = [[] for _ in range(N)]
    for _ in range(M):
        P, Q = map(int, input().split())
        P -= 1
        Q -= 1

        p0, q0 = pq[P]
        p1, q1 = pq[Q]
        d = math.sqrt((p0 - p1) ** 2 + (q0 - q1) ** 2)
        next_nodes[P].append((Q, d))
        next_nodes[Q].append((P, d))
    
    seen = [float("inf") for _ in range(N)]
    fix = [float("inf") for _ in range(N)]
    seen[X] = 0.0
    queue = []
    heapq.heappush(queue, (0.0, X))
    while len(queue) > 0:
        cost, v = heapq.heappop(queue)
        if fix[v] < float("inf"):
            continue

        fix[v] = cost
        for w, d in next_nodes[v]:
            if fix[w] < float("inf"):
                continue

            new_cost = d + cost
            if seen[w] > new_cost:
                seen[w] = new_cost
                heapq.heappush(queue, (new_cost, w))
    print(fix[Y])









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