글 읽기 - 데이터 추가 요청 드립니다.

ediya 2년 전 0

제출 번호 : 37615514

3 3

1 2 1

2 3 2

1 2 -100

ANS: -98

import sys
from collections import deque
V,E=map(int,input().split())
Edge=[]
for i in range(E):
    Edge.append(list(map(int,sys.stdin.readline().split())))

Edge.sort(key=lambda Edge: Edge[2])

def Cyclic(x):
    if Parent[x[0]]==Parent[x[1]]:
        return True
    return False

Parentdict={i:[i] for i in range(1,V+1)}
Parent=[0]*(V+1)
for i in range(V+1):
    Parent[i]=i

Ecnt=0
idx=2
ans=0

def U(x):
    global Parent,Parentdict
    if x[0]>x[1]:
        temp=[]
        for i in Parentdict[Parent[x[0]]]:
            temp.append(i)
        Parentdict[Parent[x[0]]]=[]
        for i in temp:
            Parentdict[Parent[x[1]]].append(i)
            Parent[i]=Parent[x[1]]
    else:
        temp=[]
        for i in Parentdict[Parent[x[1]]]:
            temp.append(i)
        Parentdict[Parent[x[1]]]=[]
        for i in temp:
            Parentdict[Parent[x[0]]].append(i)
            Parent[i]=Parent[x[0]]

while Ecnt<V-1:
    if Ecnt<2:
        U(Edge[Ecnt])
        ans+=Edge[Ecnt][2]
        Ecnt+=1
    else:
        while Cyclic(Edge[idx]):
            idx+=1
        U(Edge[idx])
        ans+=Edge[idx][2]
        Ecnt+=1
        idx+=1

print(ans)

startlink 2년 전 0

재채점했습니다.

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

문제

문제

출처

ICPC

데이터 추가 요청 드립니다.

ediya 2년 전 0

startlink 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말