Submission #22741

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

LM

import heapq

class Edge():
    def __init__(self, st, ed, v):
        self.st = st
        self.ed = ed
        self.value = v


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))

union = [0 for x in range(0, N+1)]
for i in range(1, N+1):
    s = 0
    # pick i to primary planet
    pick = []
    for j in range(0, N+1):
        union[j]=0
    for j in range(0, M):
        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
        else:
            heapq.heappush(pick, (edge[j].value, edge[j]))

    union[i] = i
    
    # print(union)

    # get MST
    while len(pick) > 0:
        val, eg = heapq.heappop(pick)
        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 + val
            # print("select edge [%d -> %d]" % (eg.st, eg.ed))
            # print(union)
    print(s)

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