結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
![]() |
提出日時 | 2024-09-19 23:32:50 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 610 bytes |
コンパイル時間 | 141 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 126,868 KB |
最終ジャッジ日時 | 2024-09-19 23:33:23 |
合計ジャッジ時間 | 28,714 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 2 |
other | AC * 7 WA * 39 |
ソースコード
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(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+=[(d,s,g)] e.sort() def root(x): p=x l=[p] while r[p]!=p: p=r[p] l+=[p] for p in l: r[p]=l[-1] return r[x] def union(x,y): rx=root(x) ry=root(y) if rx==ry: return if rx>ry: rx,ry=ry,rx r[ry]=rx return r=list(range(n)) C=0 for c,s,g in e: if root(s)!=root(g): union(s,g) C+=c if root(S)==root(G): break print(C)