oj.uz

Submission #22732

# Submission time Handle Problem Language Result Execution time Memory
22732 2017-04-30T07:05:25 Z 이대회 트래쉬 대회에야옹(#967, dofwk1526, HUIDONG, mincl) Logistical Metropolis (KRIII5_LM) Python 3
0 / 7
 2000 ms 103 KB 
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))


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

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 4 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2100 ms 103 KB Time limit exceeded
2 Halted 0 ms 0 KB -