day_57

53. 寻宝（第七期模拟笔试）

def main():
    v, e = map(int, input().split())
    grid = [[1e6] * (v + 1) for _ in range(v + 1)]
    for _ in range(e):
        s, t, w = map(int, input().split())
        grid[s][t] = w 
        grid[t][s] = w
    
    minDist = [1e6] * (v + 1)
    visited = [False] * (v + 1)
    for i in range(1, v + 1):
        # 找到距离图最近距离的点   
        cur = -1
        min_ = 1e6 + 1
        for j in range(1, v + 1):
            if not visited[j] and minDist[j] < min_:
                min_ = minDist[j]
                cur = j 
        # 现在更新所有图的距离
        visited[cur] = True
        for j in range(1, v + 1):
            if not visited[j] and minDist[j] > grid[cur][j]:
                minDist[j] = grid[cur][j]
    print(sum(minDist[2:]))
        
if __name__ == '__main__':
    main()

53. 寻宝（第七期模拟笔试）

def find(father, n):
    if father[n] != n:
        father[n] = find(father, father[n])
    return father[n]

def main():
    v, e = map(int, input().split())
    edges = [list(map(int, input().split())) for _ in range(e)]
    edges.sort(key=lambda edge: edge[2])
    
    father = [i for i in range(v + 1)]
    res = 0
    for s, t, w in edges:
        fs = find(father, s)
        ft = find(father, t)
        if fs != ft:
            father[fs] = ft
            res += w 
    print(res)

if __name__ == '__main__':
    main()