글 읽기 - 메모리 초과

dabbler1 1년 전 0

프림에서 다음에 들어갈 edge 후보들을 heapq에 저장하는 방식을 사용했습니다. 이 부분에서 메모리가 나간것 같은데, 이걸 개선할 방법이 있는지, 아니면 아예 다른 방식을 사용해야 할까요?

import sys; R = sys.stdin.readline
import heapq
n, m = map(int,R().split())
def find(k):
    r = root[k]
    if r!=k:
        root[k] = find(r)
    return root[k]

vertex = [(0,0)]
for _ in range(n): 
    a, b = map(float,R().split())
    vertex.append((a,b))
    
def dist(i,j):
    return ((vertex[i][0]-vertex[j][0])**2+
           (vertex[i][1]-vertex[j][1])**2)**.5
    
root = {}; edges = 0
for _ in range(m):
    u, v = map(int,R().split())
    edges += 1
    if u not in root:
        if v not in root:
            root[v] = u; root[u] = u
        else:
            root[u] = find(v)
    elif v not in root:
        root[v] = find(u)
    else:
        setu = find(u); setv = find(v)
        if setu==setv: edges -= 1
        root[setu] = setv
try: init = v
except: root[1] = 1; init = 1
        
totw = 0; covers = len(root)
nexts = []; heapq.heapify(nexts)
for _ in range(n-1-edges):
    for i in root:
        rooti = find(i)
        for j in range(1,n+1):
            if j not in root or rooti!=find(j):
                 heapq.heappush(nexts,(dist(i,j),i,j))
    i0 = init; j0 = init
    while j0 in root and (rooti:=find(i0))==(rootj:=find(j0)):
        (w,i0,j0) = heapq.heappop(nexts)
    totw += w; 
    if j0 not in root: root[j0] = rooti
    else: root[rootj] = rooti
print("%.2f"%round(totw,2))

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

문제

문제

출처

ICPC

메모리 초과

dabbler1 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말