MST문제 PRIM을 사용했고, 그중 가장 큰 경로를 삭제해주면 두개의 마을(그래프)로 분할된다는 점을 이용했다. import heapq import sys input=sys.stdin.readline n,m=map(int,input().split()) route=[[] for _ in range(n+1)] vis=[0 for _ in range(n+1)] for _ in range(m): a,b,c=map(int,input().split()) route[a].append((c,b)) route[b].append((c,a)) cost=0 maxcost=0 heap=[(0,1)] cnt=0 while heap: if cnt==n: break nowcost,now=heapq.heappop(heap) if v..
