結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
|
提出日時 | 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 |
ソースコード
""" 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()