[金貨4]4386号:星座を作成

🛠 質問する
https://www.acmicpc.net/problem/4386
👩🏻‍💻 解決策
これはすべての星の間の距離を求め、最小費用を求めるためにソートできる問題です.
星の位置を座標として入力したので、mathで星座間の距離を求めました
ソースコード

import math

def find_parent(parent, x):
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x]) 
  return parent[x]

def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)

  if a < b:
    parent[b] = a
  else:
    parent[a] = b

n = int(input())
stars = []

for _ in range(n):
  x, y = map(float, input().split())
  stars.append((x, y))

parent = [i for i in range(n)]
edges = []
result = 0

for i in range(n-1):
  for j in range(i+1, n):
    edges.append((math.sqrt((stars[i][0]-stars[j][0])**2 + (stars[i][1]-stars[j][1])**2), i, j))

edges.sort()

for edge in edges:
  cost, x, y = edge

  if find_parent(parent, x) != find_parent(parent, y):
    union_parent(parent, x, y)
    result += cost

print(round(result, 2))