結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
|
提出日時 | 2022-07-18 00:25:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 954 ms / 2,000 ms |
コード長 | 787 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 138,640 KB |
最終ジャッジ日時 | 2024-06-30 01:01:06 |
合計ジャッジ時間 | 25,104 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 |
ソースコード
import heapq N,M = map(int,input().split()) X,Y = map(int,input().split()) X,Y = X-1,Y-1 lsP = [] for i in range(N): p,q = map(int,input().split()) lsP.append((p,q)) lsG = [[] for i in range(N)] for i in range(M): P,Q = map(int,input().split()) P -= 1 Q -= 1 dist = ((lsP[P][0]-lsP[Q][0])**2+(lsP[P][1]-lsP[Q][1])**2)**(1/2) lsG[P].append((Q,dist)) lsG[Q].append((P,dist)) used = [False]*(N) inf = float('INF') lscost = [inf]*(N) lscost[X] = 0 h = [(0,X)] while h: c,n = heapq.heappop(h) if used[n]: continue used[n] = True for j,cost in lsG[n]: if used[j]: continue if lscost[j] > lscost[n] + cost: lscost[j] = lscost[n] + cost heapq.heappush(h, (lscost[j],j)) print(lscost[Y])