import sys
input = sys.stdin.readline
from heapq import heappush,heappop
from math import sqrt
N,M = map(int,input().split())
co = []
for i in range(N):
co.append([*map(int,input().split())])
graph = [[0]*N for i in range(N)]
for i in range(N-1):
x1,y1 = co[i]
for j in range(i+1,N):
x2,y2 = co[j]
d = sqrt((x1-x2)**2+(y1-y2)**2)
graph[i][j] = graph[j][i] = d
for i in range(M):
x,y = map(lambda x:x-1,map(int,input().split()))
graph[x][y] = graph[y][x] = 0
check = [0]*N
check[0] = 1
hq = []
result = 0
for i in range(N):
heappush(hq,(graph[0][i],i))
for _ in range(N-1):
while hq:
d,x = heappop(hq)
if check[x]:
continue
check[x] = 1
result += d
for i in range(N):
if check[i]:
continue
heappush(hq,(graph[x][i],i))
break
print("{:.2f}".format(result))
매우 전형적인 MST 문제이다. 프림 알고리즘으로 해결하였다.
문제를 푸는건 아주 쉬웠는데, 문제가 하나 있었다. 바로 "소수점 둘째 자리까지 출력" 이었다.
처음에는 그냥 평소 하던대로 round 함수로 반올림을 해줬는데 틀렸습니다 가 떴다.
정수를 round함수로 출력하면 4가 4.0으로 출력되는것이 문제였다.
따라서 이를 4.00으로 출력하여려면 새로운 함수인 format 함수에 대해서 알아봐야했다.
조금 짜증나는 문제였지만 앞으로 이런식의 출력을 요구하는 문제가 또 나올 수도 있으니 유의해야겠다.
오늘의 교훈) 요구사항을 잘 확인하고 format 함수를 활용하자