oj.uz

답안 #22795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22795 2017-04-30T07:31:19 Z 이대회 트래쉬 대회에야옹(#967, dofwk1526, HUIDONG, mincl) Logistical Metropolis (KRIII5_LM) Python 3
0 / 7
 2000 ms 104 KB 
import heapq

class Edge():
    def __init__(self, st, ed, v):
        self.st = st
        self.ed = ed
        self.value = v
    def __gt__(self, e2):
        return self.st < e2.st
    def __lt__(self, e2):
        return self.st > e2.st
    def __le__(self, e2):
        return self.__lt__(e2) or self.__eq__(e2)
    def __eq__(self, e2):
        return self.st == e2.st and self.ed == e2.ed
    def __ne__(self, e2):
        return not self.__eq__(e2)
    def __ge__(self, e2):
        return self.__gt__(e2) or self.__eq__(e2)


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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2040 ms 4 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2056 ms 104 KB Time limit exceeded
2 Halted 0 ms 0 KB -