# BOJ - 1647 - 도시 분할 계획

Updated:

```
import sys
import heapq
def PRIM(graph, V, idx):
hq = []
visit = [False] * (V + 1)
visit[idx] = True
distance = [0] * (V + 1)
cnt = 1
for i in graph[idx]:
heapq.heappush(hq, i)
while hq:
weight, vertex = heapq.heappop(hq)
if not visit[vertex]:
visit[vertex] = True
cnt += 1
distance[vertex] += weight
for i in graph[vertex]:
heapq.heappush(hq, i)
if cnt == V:
ret = sum(distance) - max(distance)
return ret
return 0
def solution():
V, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(V + 1)]
for _ in range(E):
A, B, C = map(int, sys.stdin.readline().split())
graph[A].append((C, B))
graph[B].append((C, A))
print(PRIM(graph, V, 1))
solution()
```

https://www.acmicpc.net/problem/1647

## Leave a comment