1140. 最短网络.py

N, n = 105, int(input())
g = [list(map(int, input().split())) for x in range(n)]
dsu = [0] * N
# 1. 根据kruskal建边
edges = [(x, y, g[x][y]) for x in range(n) for y in range(n) if g[x][y]]


def find(u):
    if u != dsu[u]:
        dsu[u] = find(dsu[u])
    return dsu[u]


def kruskal():
    path_sum, checked_edge_cnt = 0, 0
    # 1. 初始化并查集
    for i in range(1, n + 1):
        dsu[i] = i

    # 2. 边排序
    edges.sort(key=lambda e: e[2])

    # 3. 挑选边
    for u, v, w in edges:
        u, v = find(u), find(v)
        # u v 之间还没有连通
        if u != v:
            # 合并连通
            dsu[u], path_sum, checked_edge_cnt = v, path_sum + \
                w, checked_edge_cnt + 1

    # 4. 安全的返回最小路径
    return path_sum if checked_edge_cnt == n - 1 else -1


minimum_path_sum = kruskal()
print(minimum_path_sum)