글 읽기 - 왜 틀리는지 모르겠습니다.

jessi0701 3년 전 0

최소 스패닝 트리를 만들어 가면서 위성 수를 뺀 기지들이 연결될 경우 간선의 값을 출력하는 문제로 이해했는데

예제는 맞게 나오는데 50%에서 틀리네요.. 아무리 찾아봐도 안보여서 글 올립니다.

import sys
import math
from collections import deque
import copy
import heapq
#sys.stdin = open("test.txt", "r")
input=sys.stdin.readline


def find(n):
    if root_node[n] == n:
        return n
    root_node[n] = find(root_node[n])
    return root_node[n]


def union(a,b):
    x = find(a)
    y = find(b)

    if x < y :
        root_node[y] = x
    else:
        root_node[x] = y


test_case = int(input())

for _ in range(test_case):
    s, n = map(int, input().split())
    star_location = []
    Edges = []
    for i in range(n):
        x, y = map(int, input().split())
        star_location.append((x,y))

    for i in range(n-1):
        for j in range(i+1, n):
            location1 = star_location[i]
            location2 = star_location[j]

            dist = math.sqrt((abs(location1[0] - location2[0]))**2 + (abs(location1[1] - location2[1]))**2)
            Edges.append((dist, i, j))

    root_node = []
    for i in range(n):
        root_node.append(i)

    Edges.sort()
    count = 0
    res = 0
    idx = 0
    while True:
        dist, start, end = Edges[idx]

        if find(start) != find(end):
            union(start, end)
            count += 1
            res = dist

        if count == s:
            break
        idx += 1

    print("%.2f" % res)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 틀리는지 모르겠습니다.

jessi0701 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말