結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
|
提出日時 | 2020-05-29 21:35:07 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 1,465 ms / 2,000 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 2,081 ms |
コンパイル使用メモリ | 76,936 KB |
実行使用メモリ | 195,348 KB |
最終ジャッジ日時 | 2024-11-06 02:46:20 |
合計ジャッジ時間 | 32,919 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
FAST_IO = 1 if FAST_IO: import io, sys, atexit rr = iter(sys.stdin.read().splitlines()).next sys.stdout = _OUTPUT_BUFFER = io.BytesIO() @atexit.register def write(): sys.__stdout__.write(_OUTPUT_BUFFER.getvalue()) else: rr = raw_input rri = lambda: int(rr()) rrm = lambda: map(int, rr().split()) #### from collections import defaultdict as ddic import heapq def solve(N,M,X,Y,A,B): # A: powerpole locations # B: wires # Shortest path X to Y graph = ddic(list) for u, v in B: graph[u].append(v) graph[v].append(u) def dist_2d(u, v): x1, y1 = A[u - 1] x2, y2 = A[v - 1] return ((x1-x2)**2 + (y1-y2)**2)**0.5 INF = float('inf') dist = ddic(lambda: INF) dist[X] = 0 pq = [[0, X]] while pq: d, node = heapq.heappop(pq) if d > dist[node]: continue for nei in graph[node]: w = dist_2d(node, nei) d2 = d + w if d2 < dist[nei]: dist[nei] = d2 heapq.heappush(pq, [d2, nei]) return dist[Y] N,M = rrm() X,Y = rrm() A = [rrm() for _ in xrange(N)] B = [rrm() for _ in xrange(M)] print solve(N, M, X, Y, A, B)