結果

問題 No.1065 電柱 / Pole (Easy)
コンテスト
ユーザー GrayCoder
提出日時 2025-08-12 09:30:51
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,353 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 117,336 KB
最終ジャッジ日時 2025-08-12 09:32:34
合計ジャッジ時間 102,485 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1
other AC * 25 TLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

"""
from math import gcd
from itertools import accumulate, combinations, permutations, product, count
from bisect import bisect, bisect_left
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop
from functools import reduce
from operator import add, mul, sub, truediv, floordiv, mod
from sortedcontainers import SortedSet, SortedList, SortedDict

from decimal import *
getcontext().prec = 500

import string
ascii = string.ascii_lowercase
"""

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys


def main():
    input = lambda: sys.stdin.readline()[:-1]
    N, M = map(int, input().split())
    X, Y = map(int, input().split())
    _pq = np.array(list(input().split() for _ in [0] * N), dtype=np.int64)
    _PQ = np.array(list(input().split() for _ in [0] * M), dtype=np.int64)

    pq = np.transpose(_pq)
    PQ = np.transpose(_PQ)
    func = np.vectorize(lambda a, b: ((pq[0][a - 1] - pq[0][b - 1]) ** 2 + (pq[1][a - 1] - pq[1][b - 1]) ** 2) ** 0.5)
    dist = func(PQ[0], PQ[1])
    csr = csr_matrix((dist, PQ), (N + 1, N + 1))
    ans = dijkstra(csr, indices=X, directed=False)
    print(ans[Y])


if not __debug__:
    f = open(sys.argv[1], "r")
    sys.stdin = f

# try:
#     sys.set_int_max_str_digits(100000)
# except AttributeError:
#     pass

main()
0