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)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2040 ms |
4 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2056 ms |
104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
