結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
![]() |
提出日時 | 2024-09-19 23:35:50 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 520 bytes |
コンパイル時間 | 346 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 134,304 KB |
最終ジャッジ日時 | 2024-09-19 23:36:11 |
合計ジャッジ時間 | 17,620 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 2 |
other | RE * 46 |
ソースコード
n,m=map(int,input().split()) S,G=map(int,input().split()) S-=1 G-=1 p=[tuple(map(int,input().split())) for i in range(n)] e=[[] for i in range(n)] for i in range(m): s,g=map(int,input().split()) s-=1 g-=1 sx,sy=p[s] gx,gy=p[g] d=((sx-gx)**2+(sy-gy)**2)**0.5 e[s]+=[(g,d)] e[g]+=[(s,d)] from heapq import heappush,heappop v=[X]*n v[S]=0 q=[(v[S],S)] while len(q)>0: sc,sp=heappop(q) if sc>v[sp]: continue for tp,tc in e[sp]: if v[tp]>sc+tc: v[tp]=sc+tc heappush(q,(v[tp],tp)) print(v[G])