Submission #22851

#	Time	Username	Problem	Language	Result	Execution time	Memory
22851		이대회 트래쉬 대회에야옹 (#40)	Logistical Metropolis (KRIII5_LM)	Cpython 3	0 / 7	2058 ms	84 KiB

LM

import heapq
import time

class Edge():
    def __init__(self, st, ed, v):
        self.st = st
        self.ed = ed
        self.value = v
    def __gt__(self, e2):
        return self.value < e2.value
    def __lt__(self, e2):
        return self.value > e2.value
    def __le__(self, e2):
        return self.__lt__(e2) or self.__eq__(e2)
    def __eq__(self, e2):
        return self.value == e2.value
    def __ne__(self, e2):
        return not self.__eq__(e2)
    def __ge__(self, e2):
        return self.__gt__(e2) or self.__eq__(e2)
    def __repr__(self):
        return "(%d -> %d / %d)" % (self.st, self.ed, self.value)


N, M = map(lambda x: int(x), input().split(' '))

edge = []

for i in range(0, M):
    a, b, k = map(lambda x: int(x), input().split(' '))
    edge.append(Edge(a, b, k))

sorted(edge)
check = [False for x in range(0, M)]
union = [0 for x in range(0, N+1)]
for i in range(1, N+1):
    s = 0
    for j in range(0, N+1):
        union[j] = 0
    for j in range(0, M):
        check[j] = False
        if edge[j].st == i or edge[j].ed == i:
            union[edge[j].st] = i
            union[edge[j].ed] = i
            s = s + edge[j].value
            check[j] = True

    union[i] = i
    
    # print(union)

    # get MST
    for j in range(0, M):
        if check[j]:
            continue
        eg = edge[j]
        if union[eg.st] != union[eg.ed] or union[eg.st] == 0 or union[eg.ed] == 0:
            if union[eg.st] == 0 and union[eg.ed] == 0:
                union[eg.st] = eg.st
                union[eg.ed] = eg.st
            else:
                if union[eg.st] == 0:
                    union[eg.st] = union[eg.ed]
                elif union[eg.ed] == 0:
                    union[eg.ed] = union[eg.st]
                else:
                    union[eg.ed] = union[eg.st]
            s = s + eg.value
            # print("select edge [%d -> %d]" % (eg.st, eg.ed))
            # print(union)
    print(s)

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5