結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2024-11-14 21:03:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,120 ms / 2,000 ms |
コード長 | 677 bytes |
コンパイル時間 | 579 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 142,728 KB |
最終ジャッジ日時 | 2024-11-14 21:03:37 |
合計ジャッジ時間 | 28,179 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
from heapq import *N,M = map(int,input().split())X,Y = map(int,input().split())P = [list(map(int,input().split())) for _ in range(N)]E = [[] for _ in range(N)]for i in range(M):u,v = map(int,input().split())u -= 1v -= 1d = ((P[u][0] - P[v][0]) ** 2 + (P[u][1] - P[v][1]) ** 2) ** 0.5E[u].append((v,d))E[v].append((u,d))INF = 10 ** 10def dijkstra(x,y):D = [INF] * ND[x] = 0q = [(0,x)]while q:d, u = heappop(q)if d > D[u]: continuefor a,b in E[u]:if D[a] > D[u] + b:D[a] = D[u] + bheappush(q, (D[a], a))return D[y]print(dijkstra(X-1,Y-1))