Bad Cowtractors (백준 7044)

  MST를 만드는 문제인데 최소 비용이 아닌 최대 비용을 구하면 되니 힙큐에 넣을 때 가중치에 -1을 곱해서 

큰 비용을 갖고 있는 연결이 제일 앞으로 오게 만든다. 

import sys 
import heapq 
input =sys.stdin.readline
n,m = map(int, input().split())

visited= [0 for i in range(n+1)]
visited[0]  = 1 
gra = [[]for _ in range(n+1)]
for i in range(m):
    a,b,c =map(int ,input().split())
    gra[a].append((b,c))
    gra[b].append((a,c))

ans = 0
def prim(start):
    global ans 
    q = [[0,start]]
    heapq.heapify(q)
    while q :
        cost, now = heapq.heappop(q)
        if visited[now] ==0 :
            visited[now] = 1 
            ans += ((-1)*cost)
            for nextnode,nextcost in gra[now] :
                if visited[nextnode] ==0 :
                    neg = (-1)*nextcost
                    heapq.heappush(q, (neg, nextnode))
prim(1)
# ans = 
print(ans if 0 not in visited else -1 )