내가보려고만든 메자노트

문제 보러 가기 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 이 문제는 MST(최소 신장(스패닝) 트리)를 이용하여 풀 수 있었다. 크루스 칼, 프림 두 개의 알고리즘으로 풀이가 가능했고 나의 경우 프림 알고리즘으로 풀었다. 문제풀이 2개의 도시로 분할해야 하므로 프림 알고리즘을 통해 MST를 만든 후 가장 비용이 높은 간선 하나를 제거하면 2개의 도시로 나눠지고 최소 비용을 구할 수 있다. - 임의의 시작 노드를 Queue에 넣고 연결된 NodeList를 Priori..