악덕 영주 혜유(백준 20010)

먼저 MST를 만든 다음에 최소 스패닝 트리를 만들기 위해 사용한 길을 이용해 다익스트라 알고리즘을 써서 각각 지점들 사이의 거리 최댓값을 구한다. 

import sys 
import heapq 
input = sys.stdin.readline 
n,k =map(int, input().split())
inf = int(1e9)
edges = []
parent = [i for i in range(n)]

def find(a):
    if a != parent[a]:
        parent[a] = find(parent[a])
    return parent[a]     

def union(a,b):
    a =find(a)
    b = find(b)
    if a<b :
        parent[b] = a 
    else :
        parent[a] = b 
        

for i in range(k):
    a,b,c = map(int, input().split())
    edges.append((c,a,b))
edges.sort() 
# print(edges)
gra = [[]for _ in range(n)]

total = 0 
mindist =0 
for i in range(len(edges)):
    cost,a,b= edges[i] 
    a1 =find(a)
    b1 = find(b)
    if a1 == b1 :
        continue 
    else :
        union(a,b)
        gra[a].append((b, cost))
        gra[b].append((a, cost))
        total += cost
sub =0 
def dijk(start):
    dist = [inf for _ in range(n)]
    dist[start] = 0 
    q =[]
    q.append((0,start)) 
    heapq.heapify(q)
    while q :
        wei, now =heapq.heappop(q)
        if dist[now]< wei :
            continue 
        else :
            for nextnode, cost in gra[now] :
                if dist[nextnode] > wei+cost :
                    dist[nextnode] = wei+cost 
                    heapq.heappush(q,(dist[nextnode],nextnode))
    
    return dist
    
    
for k in range(n):
    arr =dijk(k) 
    sub = max(sub, max(arr))
print(total)
print(sub)