結果
問題 | No.1639 最小通信路 |
ユーザー |
![]() |
提出日時 | 2024-06-30 18:45:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 418 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,852 KB |
実行使用メモリ | 77,384 KB |
最終ジャッジ日時 | 2024-06-30 18:46:03 |
合計ジャッジ時間 | 4,963 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
def root(x):p=xl=[p]while r[p]!=p:p=r[p]l.append(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:rx,ry=ry,rxr[ry]=rxreturnn=int(input())e=[]for i in range((n*(n-1))//2):a,b,c=map(int,input().split())a-=1b-=1e+=[(c,a,b)]e.sort()l=0r=list(range(n))for c,a,b in e:if root(a)!=root(b):union(a,b)l=cprint(l)