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