結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 21:44:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 852 bytes |
コンパイル時間 | 145 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 114,048 KB |
最終ジャッジ日時 | 2024-11-06 03:23:27 |
合計ジャッジ時間 | 58,910 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 TLE * 12 |
ソースコード
import heapq N,M = map(int, input().split()) X,Y = map(int, input().split()) L = [[int(l) for l in input().split()] for _ in range(N)] E = [[] for _ in range(N)] for _ in range(M): p,q = map(int, input().split()) p -= 1 q -= 1 d = ((L[p][0]-L[q][0])**2 + (L[p][1]-L[q][1])**2)**0.5 E[p].append((q, d)) E[q].append((p, d)) def dijkstra(s): used = [0]*N inf = 10**12 d = [inf]*N used[s] = 1 d[s] = 0 h = [] for e in E[s]: heapq.heappush(h, (e[1], e[0])) while h: temp = heapq.heappop(h) u = temp[1] r = temp[0] if used[u] == 1: continue d[u] = r used[u] = 1 for e in E[u]: if used[e[0]] == 1: continue heapq.heappush(h, (r+e[1], e[0])) return d d = dijkstra(X-1) print(d[Y-1])