結果

問題 No.1639 最小通信路
ユーザー flippergo
提出日時 2025-02-27 14:02:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 417 ms / 2,000 ms
コード長 953 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 81,104 KB
最終ジャッジ日時 2025-02-27 14:03:05
合計ジャッジ時間 7,458 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
M = (N*(N-1))//2
A = [list(map(int,input().split())) for _ in range(M)]
T = [[i,0] for i in range(N+1)]
def find(x):
    if T[x][0]==x:
        return x
    return find(T[x][0])
def unite(x,y):
    rx = find(x)
    ry = find(y)
    if rx==ry:
        return
    if T[rx][1]>T[ry][1]:
        T[ry][0] = rx
    elif T[rx][1]<T[ry][1]:
        T[rx][0] = ry
    else:
        T[rx][0] = ry
        T[ry][1] += 1
high = A[-1][2]+1
low = 0
cmin = M*high
while high-low>1:
    mid = (high+low)//2
    cost = 0
    cnt = 0
    T = [[i,0] for i in range(N+1)]
    for i in range(M):
        a,b,c = A[i]
        if c>mid:break
        ra = find(a)
        rb = find(b)
        if ra!=rb:
            unite(ra,rb)
            cost += c
            cnt += 1
        if cnt==N-1:break
    if cnt<N-1:
        low = mid
    else:
        if cost<=cmin:
            cmin = cost
            high = mid
        else:
            low = mid
print(high)
0