結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | McGregorsh |
提出日時 | 2023-07-12 21:15:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,016 ms / 2,000 ms |
コード長 | 1,966 bytes |
コンパイル時間 | 620 ms |
コンパイル使用メモリ | 87,236 KB |
実行使用メモリ | 170,652 KB |
最終ジャッジ日時 | 2023-10-12 11:17:15 |
合計ジャッジ時間 | 33,142 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 237 ms
90,092 KB |
testcase_01 | AC | 236 ms
89,956 KB |
testcase_02 | AC | 685 ms
131,944 KB |
testcase_03 | AC | 801 ms
170,432 KB |
testcase_04 | AC | 782 ms
169,624 KB |
testcase_05 | AC | 634 ms
170,652 KB |
testcase_06 | AC | 631 ms
170,564 KB |
testcase_07 | AC | 333 ms
112,124 KB |
testcase_08 | AC | 529 ms
168,020 KB |
testcase_09 | AC | 288 ms
97,248 KB |
testcase_10 | AC | 386 ms
125,960 KB |
testcase_11 | AC | 339 ms
111,724 KB |
testcase_12 | AC | 317 ms
106,020 KB |
testcase_13 | AC | 763 ms
145,892 KB |
testcase_14 | AC | 818 ms
153,944 KB |
testcase_15 | AC | 916 ms
162,184 KB |
testcase_16 | AC | 585 ms
127,612 KB |
testcase_17 | AC | 952 ms
168,964 KB |
testcase_18 | AC | 483 ms
117,880 KB |
testcase_19 | AC | 899 ms
164,028 KB |
testcase_20 | AC | 439 ms
111,580 KB |
testcase_21 | AC | 517 ms
124,700 KB |
testcase_22 | AC | 887 ms
156,956 KB |
testcase_23 | AC | 248 ms
91,228 KB |
testcase_24 | AC | 252 ms
91,560 KB |
testcase_25 | AC | 309 ms
105,724 KB |
testcase_26 | AC | 601 ms
131,176 KB |
testcase_27 | AC | 649 ms
132,456 KB |
testcase_28 | AC | 908 ms
158,012 KB |
testcase_29 | AC | 359 ms
101,872 KB |
testcase_30 | AC | 912 ms
163,280 KB |
testcase_31 | AC | 704 ms
142,040 KB |
testcase_32 | AC | 577 ms
125,184 KB |
testcase_33 | AC | 1,016 ms
163,036 KB |
testcase_34 | AC | 529 ms
118,928 KB |
testcase_35 | AC | 906 ms
163,820 KB |
testcase_36 | AC | 262 ms
91,340 KB |
testcase_37 | AC | 297 ms
93,328 KB |
testcase_38 | AC | 268 ms
92,640 KB |
testcase_39 | AC | 298 ms
93,488 KB |
testcase_40 | AC | 246 ms
90,384 KB |
testcase_41 | AC | 990 ms
168,980 KB |
testcase_42 | AC | 491 ms
116,044 KB |
testcase_43 | AC | 645 ms
133,812 KB |
testcase_44 | AC | 407 ms
107,608 KB |
testcase_45 | AC | 635 ms
131,796 KB |
testcase_46 | AC | 234 ms
89,992 KB |
testcase_47 | AC | 232 ms
90,104 KB |
ソースコード
###ダイクストラ### def daikusutora(N, G, s): dist = [INF] * N que = [(0, s)] dist[s] = 0 while que: c, v = heappop(que) if dist[v] < c: continue for t, cost in G[v]: if dist[v] + cost < dist[t]: dist[t] = dist[v] + cost heappush(que, (dist[t], t)) return dist import sys from sys import stdin from fractions import Fraction import math from math import ceil, floor, sqrt, pi, factorial, gcd from copy import deepcopy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import accumulate, product, combinations, combinations_with_replacement, permutations from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from decimal import Decimal, getcontext, ROUND_HALF_UP def i_input(): return int(stdin.readline()) def i_map(): return map(int, stdin.readline().split()) def i_list(): return list(i_map()) def s_input(): return stdin.readline()[:-1] def s_map(): return s_input().split() def s_list(): return list(s_map()) def lcm(a, b): return a * b // gcd(a, b) def get_distance(x1, y1, x2, y2): d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) return d def rotate(table): n_fild = [] for x in zip(*table[::-1]): n_fild.append(x) return n_fild sys.setrecursionlimit(10 ** 7) INF = float('inf') MOD = 10 ** 9 + 7 MOD2 = 998244353 alpa = 'abcdefghijklmnopqrstuvwxyz' ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' def main(): N, M = i_map() X, Y = i_map() X -= 1 Y -= 1 nums = [i_list() for i in range(N)] G = [[] for i in range(N)] for i in range(M): p, q = i_map() p -= 1 q -= 1 ax, ay = nums[p] bx, by = nums[q] cost = get_distance(ax, ay, bx, by) G[p].append([q, cost]) G[q].append([p, cost]) ans = daikusutora(N, G, X) print(ans[Y]) if __name__ == '__main__': main()