정복자(백준 14950)

 

  프림 알고리즘을 이용해서 도시들을 모두 이어준 다음에 나중에 추가 비용을 더하면 된다. 

크루스칼 알고리즘을 이용해도 된다. 

14950번: 정복자

import sys
import heapq
input = sys.stdin.readline 
n,m,t = map(int, input().split())
visit = [0 for i in range(n+1)]
gra = [[] for i in range(n+1)]
ans = 0 

def prim(start):
    global ans 
    q = [[0,start]]
    flag = 0 
    heapq.heapify(q)
    while q:
        cost, now= heapq.heappop(q)
        flag += 1 
        if visit[now]==0 :
            visit[now] = 1 
            ans+= cost 
            for nextnode, nextcost in gra[now] :
                if visit[nextnode] ==0 :
                    heapq.heappush(q, (nextcost ,nextnode))
plus = (n-1)*(n-2)//2 

for i in range(m):
    a,b,c= map(int, input().split())
    gra[a].append((b,c))
    gra[b].append((a,c))

prim(1)
ans += plus*t 
print(ans)