結果
問題 | No.1639 最小通信路 |
ユーザー |
![]() |
提出日時 | 2021-08-06 21:52:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 862 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 76,572 KB |
最終ジャッジ日時 | 2024-09-17 01:47:57 |
合計ジャッジ時間 | 3,504 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
import sys from sys import stdin import heapq def uf_find(n,p): ufl = [] while p[n] != n: ufl.append(n) n = p[n] for i in ufl: p[i] = n return n def uf_union(a,b,p,rank): ap = uf_find(a,p) bp = uf_find(b,p) if ap == bp: return True else: if rank[ap] > rank[bp]: p[bp] = ap elif rank[ap] < rank[bp]: p[ap] = bp else: p[bp] = ap rank[ap] += 1 return False N = int(stdin.readline()) CAB = [] for i in range(N*(N-1)//2): a,b,c = map(int,stdin.readline().split()) CAB.append((c,a-1,b-1)) CAB.sort() p = [i for i in range(N)] rank = [0] * N rem = N-1 for i in range(len(CAB)): c,a,b = CAB[i] if not uf_union(a,b,p,rank): rem -= 1 if rem == 0: print (c) break