5249. 최소 신장 트리 ( Prim , 프림 알고리즘)

'''
1
2 3
0 1 1
0 2 1
1 2 6
1
4 7
0 1 9
0 2 3
0 3 7
1 4 2
2 3 8
2 4 1
3 4 8
프림
'''
def prim(start):
    # 시작점 설정 ( 가중치 0으로 )
    total = 0
    u = 0   # 가중치가 최소인 정점
    dist[u] = 0
    # 정점의 갯수만큼 반복
    for i in range(V+1):
        # 가중치 최소값 찾기
        min = 987654321
        for v in range(V+1):
            if visited[v] == 0 and min > dist[v]:
                min = dist[v]
                u = v   # 최소값
 
        # 방문처리
        visited[u] = 1
        total += adj[PI[u]][u]
 
        # 인접 정점에 업데이트하기
        for v in range(V+1):
            # 인접하고 방문 안하고 간선의 가중치 정점의 가중치를 비교
            if adj[u][v] != 0 and visited[v] == 0 and adj[u][v] < dist[v]:
                ######################################-------------------##
                dist[v] = adj[u][v] # 가중치
                #------------------#
                PI[v] = u
 
    return total
 
 
T = int(input())
for tc in range(1, T+1):
    V, E = map(int, input().split())
 
    adj = [[0] * (V+1) for _ in range(V+1)]
    dist = [987654321] * (V+1)
    PI = list(range(V+1))
    visited = [0] * (V+1)
 
    for i in range(E):
        node_t = list(map(int, input().split()))
        #print(node_t)
        adj[node_t[0]][node_t[1]] = node_t[2]
        adj[node_t[1]][node_t[0]] = node_t[2]
    #print(node_t)
    result = prim(0)
    print("#{} {}".format(tc, result))