Problem:


Minimum Spanning Tree

Find the sum of weights of edges of the Minimum Spanning Tree for a given weighted undirected graph G = (V, E).

Input

|V| |E|
s0 t0 w0
s1 t1 w1
:
s|E|-1 t|E|-1 w|E|-1

, where |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively.

si and ti represent source and target verticess of i-th edge (undirected) and wi represents the weight of the i-th edge.

Output

Print the sum of the weights of the Minimum Spanning Tree.

Constraints

1 ≤ |V| ≤ 10,000

0 ≤ |E| ≤ 100,000

0 ≤ wi ≤ 10,000

The graph is connected

There are no parallel edges

There are no self-loops

Sample Input 1

4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5

Sample Output 1

3

Sample Input 2

6 9
0 1 1
0 2 3
1 2 1
1 3 7
2 4 1
1 4 3
3 4 1
3 5 1
4 5 6

Sample Output 2

5



Sample input:
4 6
0 1 2
1 2 1
2 3 1
3 0 1
0 2 3
1 3 5


Sample output:
3

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
V=0
E=0
edge=[]
p=[]
rank=[]
answer=0
count=0

def makeset(x):
    p[x] = x
    rank[x] = 0
    
def union(x,y):
    link(findset(x),findset(y))
    
def link(x,y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] = rank[y] + 1
            
def findset(x):
    if x != p[x]:
        p[x] = findset(p[x])
    return p[x]
            
def takeThird(elem):
    return elem[2]
v,e = map(int,input().split())
V=v
E=e
while True:
    try:
        s,t,w = map(int,input().split())
    except:
        break
    else:
        edge.append([s,t,w])
        
edge.sort(key=takeThird)
for i in range(V):
    p.append(None)
    rank.append(None)
for i in range(V):
    makeset(i)
for i in range(len(edge)):
    if count == V-1:
        break
    if(findset(edge[i][0]) == edge[i][1]):
        continue
    union(edge[i][0],edge[i][1])
    answer+=edge[i][2]
    count+=1
    
print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

# クラスカル法を使う

V, E = map(int, input().split())
D = 0
vertices = []
for i in range(V):
    vertices.append(i)          # 全ての頂点は自分の頂点 index と同じ index の木に属す

edges = []
for i in range(E):
    s, t, d = map(int, input().split())
    edges.append((s, t, d))

edges.sort(key=lambda x: x[2])
while edges:
    if V == 0:
        break
    s, t, d = edges.pop(0)
    if vertices[s] != vertices[t]:
        vertices[s] = vertices[t] = min(vertices[s], vertices[t])
        D += d
        V -= 1
print(D)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
# クラスカル法を使う

V, E = map(int, input().split())
D = 0
tree = []
vertices = defaultdict(set)
for i in range(V):
    tree.append(i)          # 全ての頂点は自分の頂点 index と同じ index の木に属す
    vertices[i].add(i)

edges = []
for i in range(E):
    s, t, d = map(int, input().split())
    edges.append((s, t, d))

edges.sort(key=lambda x: x[2])
while edges:
    if V == 1:
        break
    s, t, d = edges.pop(0)
    if tree[s] != tree[t]:
        new = min(tree[s], tree[t])
        old = max(tree[s], tree[t])
        tree[s] = new
        tree[t] = new
        vertices[new] = vertices[new] & vertices[old]
        for vertex in vertices[new]:
            tree[vertex] = new

        D += d
        V -= 1
print(D)

Submission status: Wrong Answer

Solution code:
def find_tree(v):
    for tree in forest:
        if v in tree:
            return tree

nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find_tree(s)
    v = find_tree(t)
    if u != v:
        [u.append(i) for i in v]
        forest.remove(v)
        sum += w
    if len(forest) == 1:
        print(sum)
        exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)

for e in range(edges):
    source,target,w = map(int,input().split(" "))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = set()
now_weight = 0

while len(went) < vertices:
    now_weight,here = heapq.heappop(queue)
    #print(now_weight,here)
    can_go = link.get(here,set()) - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        if min_weight > now_weight + weight[here][c]:
            min_weight = now_weight + weight[here][c]
            next_t = c
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
    heapq.heappush(queue,[min_weight,next_t])
    #print(queue)
    went = went | {here}
print(now_weight)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
for e in range(edges):
    source,target,w = map(int,input().split(" "))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = [0] * vertices
now_weight = 0
way[0] = 0

while len(went) < vertices:
    here_weight,here = heapq.heappop(queue)
    if here in went:
        continue
    #print(now_weight,here)
    went[here] = 1
    now_weight += here_weight
    can_go = link.get(here,set()) - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
        if c not in went and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    #print(queue)
print(now_weight)

Submission status: Wrong Answer

Solution code:
import sys


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.p = [i for i in range(n + 5)]
        self.rank = [0 for i in range(n + 5)]

    def find_set(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]

    def unite(self, x, y):
        px, py = self.find_set(x), self.find_set(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:
            self.p[y] = px
        else:
            self.p[x] = py
            if self.rank[px] == self.rank[py]:
                self.rank[py] += 1


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    E = []
    uf = UnionFind(nvertices)
    for i in range(nedges):
        s, t, w = map(int, input().split())
        E.append((w, s, t))
    E.sort()
    for e in E:
        print(e)
    ans = 0
    for w, s, t in E:
        if uf.find_set(s) != uf.find_set(t):
            ans += w
            uf.unite(s, t)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.p = [i for i in range(n + 5)]
        self.rank = [0 for i in range(n + 5)]

    def find_set(self, x):
        if self.p[x] != x:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]

    def unite(self, x, y):
        px, py = self.find_set(x), self.find_set(y)
        if px == py:
            return
        if self.rank[px] > self.rank[py]:
            self.p[y] = px
        else:
            self.p[x] = py
            if self.rank[px] == self.rank[py]:
                self.rank[py] += 1


def main():
    sys.setrecursionlimit(int(1e5))
    nvertices, nedges = map(int, input().split())
    E = []
    uf = UnionFind(nvertices)
    for i in range(nedges):
        s, t, w = map(int, input().split())
        E.append((w, s, t))
    E.sort()

    ans = 0
    for w, s, t in E:
        if uf.find_set(s) != uf.find_set(t):
            ans += w
            uf.unite(s, t)

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline


class UnionFind:
    __slots__ = ["nodes"]

    def __init__(self, n: int) -> None:
        self.nodes = [-1]*n

    def get_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            bigroot, smallroot = \
                (root_x, root_y) if self.nodes[root_x] < self.nodes[root_y] else (root_y, root_x)
            self.nodes[bigroot] += self.nodes[smallroot]
            self.nodes[smallroot] = bigroot
            return True
        else:
            return False


def kruskal(n: int, edges: list) -> int:
    edges.sort()
    tree = UnionFind(n)
    total = 0
    for w, s, t in edges:
        if tree.unite(s, t):
            total += w

    return total


V, E = map(int, readline().split())
edges = []
append = edges.append
for _ in [None]*E:
    s, t, w = map(int, readline().split())
    append((w, s-1, t-1))
print(kruskal(V, edges))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

INF = float('inf')


V, E = map(int, input().split())
Adj_list = defaultdict(set)

for i in range(E):
    s, t, w = map(int, input().split())
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def prim(x):
    d = [INF] * x
    d[0] = 0
    hq = [(0,0)] 
    
    while hq:
        u = heapq.heappop(hq)[1]
        for v, c in Adj_list[u]:
            if d[v] > c:
                d[v] = c
                heapq.heappush(hq, (c, v))
    return sum(d)

print(prim(V))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import heapq
vertices, edges = (int(n) for n in input().split(" "))
conn = defaultdict(set)
weight = defaultdict(dict)
for i in range(edges):
    v1, v2, w = (int(n) for n in input().split(" "))
    conn[v1] |= {v2}
    conn[v2] |= {v1}
    weight[v1][v2] = w
    weight[v2][v1] = w

queue = []
heapq.heapify(queue)
heapq.heappush(queue, [0,0])
went = set()
went_vertices = 0
answer_weight = 0
while went_vertices < vertices:
    here_v, here_weight = heapq.heappop(queue)
    if here_v in went:
        continue
    went |= {here_v}
    for c in conn[here_v]:
        if c not in went:
            heapq.heappush(queue,[c, weight[here_v][c]])
    answer_weight += here_weight
    went_vertices += 1
print(answer_weight)

Submission status: Wrong Answer

Solution code:
import sys
import collections

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])
    
V, E = map(int, sys.stdin.readline().split())
edges = sorted([Edge(*map(int, line.split())) for line in sys.stdin], key=lambda e: e.cost)
uf = UnionFind(V)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
min_cost

Submission status: Wrong Answer

Solution code:
# Sliding Minimum Elements
INF = 2**31 - 1
[n, l] = list(map(int, input().split()))
data = list(map(int, input().split()))


def initRMQ(tree):
    global n
    size = 1
    while size < l:
        size *= 2
    i = 1
    while i <= 2*size - 1 - 1:
        tree.append(INF)
        i += 1
    n = size
    return tree

def update(k, a, temp):
    k += n - 1
    temp[k:k+l] = a
    for i in range(k, k+l, 2):
        while i > 0:
            i = int((i - 1)/2)
            temp[i] = min(temp[i*2 + 1], temp[i*2 + 2])


index = 0
array = initRMQ([INF])
while (len(data) - index - l) >= 0:
    #temp = list(array)
    #update(0, data[index:index+l], temp)
    temp = data[index:index+l]
    temp.sort()
    index += 1
    if (len(data) - index - l) < 0:
        print(temp[0])
    else:
        print(temp[0], "", end="")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

line = input()
v, e = list(map(int, line.split()))
edge = []
for _ in range(0, e):
    line = input()
    s, t, w = list(map(int, line.split()))
    edge += [[s, t, w]]

def solve(v, edge):
    q = []
    vtx = set([i for i in range(0, v)])
    for s, t, w in edge:
        heappush(q, (w, (s, t)))
    vn = set([0])
    en = []
    cost = 0
    while vn != vtx:
        w = s = t = 0
        qq = []
        while q:
            w, st = heappop(q)
            s, t = st
            if s in vn and t not in vn:
                break
            if s not in vn and t in vn:
                s, t = t, s
                break
            qq += [[s, t, w]]
        for s, t, w in qq:
            heappush(q, (w, (s, t)))
        vn.add(t)
        en += [(s, t)]
        cost += w
    return cost
        
print(solve(v, edge))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

line = input()
v, e = list(map(int, line.split()))
edge = []
for _ in range(0, e):
    line = input()
    s, t, w = list(map(int, line.split()))
    edge += [[s, t, w]]

def solve(v, edge):
    q = []
    vtx = set([i for i in range(0, v)])
    for s, t, w in edge:
        heappush(q, (w, (s, t)))
    vn = set([0])
    en = []
    cost = 0
    while vn != vtx:
        w = s = t = 0
        qq = []
        while q:
            w, st = heappop(q)
            s, t = st
            if s in vn and t not in vn:
                break
            if s not in vn and t in vn:
                s, t = t, s
                break
            qq += [[s, t, w]]
        vn.add(t)
        en += [(s, t)]
        cost += w
        for s, t, w in qq:
            heappush(q, (w, (s, t)))
    return cost
        
print(solve(v, edge))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

V, E = list(map(int, input().split()))
weight = []
for i in range(E):
  s, t, w = list(map(int, input().split()))
  weight.append((s,t,w))

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]

def find(x):
  if parent[x] == x:
    return x
  else:
    return find(parent[x])

def union(x, y):
  a = find(x)
  b = find(y)
  parent[a] = b
  

sum_weight = 0

while weight:
  a, b, c = weight[0]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  weight.pop(0)
  
print(sum_weight)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

V, E = list(map(int, input().split()))
weight = []
for i in range(E):
  s, t, w = list(map(int, input().split()))
  weight.append((s,t,w))

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]

def find(x):
  if parent[x] == x:
    return x
  else:
    return find(parent[x])

def union(x, y):
  a = find(x)
  b = find(y)
  parent[a] = b
  

sum_weight = 0

for i in range(E):
  a, b, c = weight[i]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  else:
    continue
  
print(sum_weight)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def prim(g, v):
    for vi in range(v):
        g[vi].sort()
    
    cost = 0
    heap = iter(g[0])
    rest_tree = set(range(1, v))
    while rest_tree:
        d, u = next(heap)
        if u in rest_tree:
            cost += d
            rest_tree -= {u}
            heap = heapq.merge(heap, g[u])
    return cost

from sys import stdin
readline = stdin.readline


v, e = map(int, readline().split())
from collections import defaultdict
g = defaultdict(list)
for _ in range(e):
    s, t, d = map(int, readline().split())
    g[s].append((d, t))
    g[t].append((d, s))

print(prim(g, v))

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
INF = 1000000000

class Edge:
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost

def get_belonged_cluster(clust, vertex):
	for i, c in enumerate(clust):
		if vertex in c:
			return i


def kruskal(graph):
	V = len(graph)
	cluster = [[i] for i in xrange(V)]

	pq = []
	for i, node in enumerate(graph):
		for edge in node:
			heapq.heappush(pq, (edge.cost, i, edge.to))


	tree = []

	while len(pq) != 0:
		_edge = heapq.heappop(pq)

		_from = _edge[1]
		_to = _edge[2]
		cluster_from = get_belonged_cluster(cluster, _from)
		cluster_to = get_belonged_cluster(cluster, _to)
		# print cluster
		# print _edge
		# print cluster_from, cluster_to
		# print

		if cluster_from != cluster_to:
			tree.append(_edge[0])
			cluster[cluster_from].extend(cluster[cluster_to])
			cluster.pop(cluster_to)

	return tree



 

def main():
	V, E = map(int, raw_input().split())

	graph = [[] for _ in xrange(V)]
	for i in xrange(E):
		_s, _t, _c = map(int, raw_input().split())
		graph[_s].append(Edge(_t, _c))


	tree = kruskal(graph)
	print sum(tree)


if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
# クラスカル法を使う

V, E = map(int, input().split())
D = 0
tree = []
vertices = defaultdict(set)
for i in range(V):
    tree.append(i)          # 全ての頂点は自分の頂点 index と同じ index の木に属す
    vertices[i].add(i)

edges = []
for i in range(E):
    s, t, d = map(int, input().split())
    edges.append((s, t, d))

edges.sort(key=lambda x: x[2])
while edges:
    if V == 1:
        break
    s, t, d = edges.pop(0)
    if tree[s] != tree[t]:
        new = min(tree[s], tree[t])
        old = max(tree[s], tree[t])
        vertices[new] = vertices[new] | vertices[old]
        for vertex in vertices[new]:
            tree[vertex] = new

        D += d
        V -= 1
print(D)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    while pq:
        _, u = heapq.heappop(pq)
        for v, v_cost in adj_list[u]:
            if v in (item[1] for item in pq):
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
    return (pred, key)


def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim?????§??????0?????????????°???¨?????¨????±???????
def compute_mst_prim(max_v, adj_list):
    # pred[u]?????????u???????????¨???????????????????????¨???
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # u??¨pred[u]????????¶???????????????key[u]?????\???
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # ??????????????????????????????????????\?????¨????????¨??????
    pq = []
    for v in range(max_v):
        heapq.heappush(pq, (key[v], v))
    while pq:
        _, u = heapq.heappop(pq)
        for v, v_cost in adj_list[u]:
            if v in (item[1] for item in pq):
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
    return (pred, key)


def main():
    max_v, max_e = map(int, input().split())
    adjacency_list = collections.defaultdict(set)
    for _ in range(max_e):
        s, t, w = map(int, input().split())
        adjacency_list[s].add(AdjacentVertex(t, w))
        adjacency_list[t].add(AdjacentVertex(s, w))
    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
  def __init__(self, size):
    self.table = [-1 for _ in xrange(size)]

  def find(self, x):
    while self.table[x] >= 0: x = self.table[x]
    return x

  def union(self, x, y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] >= self.table[s2]:
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
      else:
        self.table[s2] += self.table[s1]
        self.table[s1] = s2
      return True
    return False

def hash(n, s, g):
  return n*s+g

def dehash(n, hs):
  return [(hs-hs%n)/n, hs%n]

def kruskal(n, path):
  path = sorted(path.items(), key=lambda x:x[1])
  selected = {}
  union = UnionFind(n)
  for i in xrange(len(path)):
    k,v = path[i]
    s,g = dehash(n, k)
    if union.union(s, g):
      selected[k] = v
  return selected

V,E = map(int, raw_input().split())
path = {}
for _ in xrange(E):
  s,t,w = map(int, raw_input().split())
  path[hash(V, s, t)] = w
result = kruskal(V, path)
sumcost = 0
for v in result.values():
  sumcost += v
print sumcost

Submission status: Time Limit Exceeded

Solution code:
def find_tree(v):
    for tree in forest:
        if v in tree:
            return tree

nv, ne = map(int, input().split(' '))
edges = []
for i in range(ne):
    s, t, w = map(int, input().split(' '))
    edges.append((s, t, w))

sum = 0
forest = [[v] for v in range(nv)]
edges.sort(key=lambda tup: tup[2])
for s, t, w in edges:
    u = find_tree(s)
    v = find_tree(t)
    if u != v:
        [u.append(i) for i in v]
        forest.remove(v)
        sum += w
    if len(forest) == 1:
        break

print(sum)
exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq

vertices,edges = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
way = [float("inf")] * vertices
for e in range(edges):
    source,target,w = map(int,input().split(" "))
    link[source] = link.get(source,set()) | {target}
    link[target] = link.get(target,set()) | {source}
    weight[source].update({target:w})
    weight[target].update({source:w})
queue = []
heapq.heapify(queue)
heapq.heappush(queue,[0,0])
went = set()
now_weight = 0
way[0] = 0

while len(went) < vertices:
    here_weight,here = heapq.heappop(queue)
    #print(now_weight,here)
    now_weight += here_weight
    can_go = link.get(here,set()) - went
    min_weight,next_t = float("inf"),-1
    for c in can_go:
        #heapq.heappush(queue,[now_weight + weight[here][c],c])
        if c not in went and way[c] > weight[here][c]:
            heapq.heappush(queue,[weight[here][c],c])
            way[c] = weight[here][c]
    #print(queue)
    went = went | {here}
print(now_weight)

Submission status: Time Limit Exceeded

Solution code:
n,E = map(int, input().split())
M = [[] for i in range(n)]
for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])
 M[t].append([s,w])

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0
 
 while True:
  minv = float("inf")
  u = -1
  for i in range(n):
   if minv > d[i] and color[i] != 2:
    u = i
    minv = d[i]
  if u == -1: break
  color[u] = 2
  for v1, v2 in M[u]:
   if color[v1] != 2:
    if d[v1] > v2:
     d[v1] = v2
 return sum(d)
 
print(prim())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
INF = 9999999999999999999999999999

def spanning_tree(G):
  n = len(G)
  T = {}
  added = set()
  min_c = INF
  for i in G:
    for j in G[i]:
      if G[i][j] < min_c:
        min_c = G[i][j]
        min_e = (i, j)
  T[min_e] = min_c
  added.add(min_e[0])
  added.add(min_e[1])
  while len(added) < n:
    min_c = INF
    for u in added:
      for v in G[u]:
        if v in added:
          continue
        if G[u][v] < min_c:
          min_c = G[u][v]
          min_e = (u, v)
    T[min_e] = min_c
    added.add(min_e[1])
  return T


G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c
  G[t][s] = c

if m == 0:
  print(0)
  exit()

T = spanning_tree(G)

s = 0
for e in T:
  s += T[e]

print(s)

Submission status: Memory Limit Exceeded

Solution code:
INF = 10000


class MinSpandTree():
    def __init__(self, n, cost):
        self.v = n
        self.cost = cost
        self.used = [False for i in range(n)]
        self.mincost = [INF for i in range(n)]

    def prim(self):
        self.mincost[0] = 0
        ans = 0
        while True:
            v = -1
            for u in range(self.v):
                # print("u = {}, mincost[u] = {}, v = {}, mincost[v] = {}".format(u, self.mincost[u], v, self.mincost[v]))
                if not self.used[u] and (v == -1 or self.mincost[u] < self.mincost[v]):
                    # print("v changed to {}".format(u))
                    v = u

            if v == -1:
                break
            self.used[v] = True
            ans += self.mincost[v]

            # 経路に応じて最小を初期化する
            for u in range(self.v):
                # 新しくセットした経路から少ないコストの経路がないのかを探す、更新する
                self.mincost[u] = min(self.mincost[u], self.cost[v][u])
                # print(min(self.mincost[u], self.cost[v][u]))

        return ans


V, E = map(lambda x: int(x), input().split())
array = [[INF for i in range(V)] for i in range(V)]
for _ in range(E):
    a, b, cost = map(lambda x: int(x), input().split())
    array[a][b] = cost
    array[b][a] = cost
min_spand_tree = MinSpandTree(V, array)
print(min_spand_tree.prim())

Submission status: Memory Limit Exceeded

Solution code:
import sys


WHITE = 0
GRAY = 1
BLACK = 2
INF = 10001

line = sys.stdin.readline()
n, e = map(int, line.split())

color = [WHITE for _ in range(n)]
M = [[-1 for _ in range(n)] for _ in range(n)]
d = [INF for _ in range(n)]
p = [-1 for _ in range(n)]


def prim():
    d[0] = 0
    p[0] = -1

    while 1:
        mincost = INF
        for i in range(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF:
            break

        color[u] = BLACK

        for v in range(n):
            if color[v] != BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY


for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    M[s][t] = w
    M[t][s] = w
prim()
print(sum(d))

Submission status: Memory Limit Exceeded

Solution code:
import sys


WHITE = 0
GRAY = 1
BLACK = 2
INF = 10001

line = sys.stdin.readline()
n, e = map(int, line.split())

color = [WHITE for _ in range(n)]
M = [[-1] * n for _ in range(n)]
d = [INF for _ in range(n)]
p = [-1 for _ in range(n)]


def prim():
    d[0] = 0
    p[0] = -1

    while 1:
        mincost = INF
        for i in range(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF:
            break

        color[u] = BLACK

        for v in range(n):
            if color[v] != BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY


for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    M[s][t] = w
    M[t][s] = w
prim()
print(sum(d))

Submission status: Memory Limit Exceeded

Solution code:
import sys


WHITE = 0
GRAY = 1
BLACK = 2
INF = 10001

line = sys.stdin.readline()
n, e = map(int, line.split())

color = [WHITE for _ in range(n)]
M = [[-1] * n for _ in range(n)]
d = [INF for _ in range(n)]
p = [-1 for _ in range(n)]


def prim():
    d[0] = 0
    p[0] = -1
    res = 0

    while 1:
        mincost = INF
        for i in range(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF:
            break

        res += d[u]
        color[u] = BLACK

        for v in range(n):
            if color[v] != BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY

    return res


for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    M[s][t] = w
    M[t][s] = w
print(prim())

Submission status: Memory Limit Exceeded

Solution code:
import sys


WHITE = 0
GRAY = 1
BLACK = 2
INF = 10001

line = sys.stdin.readline()
n, e = map(int, line.split())

color = [WHITE for _ in range(n)]
# M = [[-1] * n for _ in range(n)]
d = [INF for _ in range(n)]
p = [-1 for _ in range(n)]

M = {}
for i in range(n):
    M[i] = {}
    for j in range(n):
        M[i][j] = -1


def prim():
    d[0] = 0
    p[0] = -1
    res = 0

    while 1:
        mincost = INF
        for i in range(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF:
            break

        res += d[u]
        color[u] = BLACK

        for v in range(n):
            if color[v] != BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY

    return res


for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    M[s][t] = w
    M[t][s] = w
print(prim())

Submission status: Memory Limit Exceeded

Solution code:
import sys
from array import array


WHITE = 0
GRAY = 1
BLACK = 2
INF = 10001

line = sys.stdin.readline()
n, e = map(int, line.split())

color = array('i', [WHITE for _ in range(n)])
M = [[-1] * n for _ in range(n)]
d = array('i', [INF for _ in range(n)])
p = array('i', [-1 for _ in range(n)])


def prim():
    d[0] = 0
    p[0] = -1
    res = 0

    while 1:
        mincost = INF
        for i in range(n):
            if color[i] != BLACK and d[i] < mincost:
                mincost = d[i]
                u = i

        if mincost == INF:
            break

        res += d[u]
        color[u] = BLACK

        for v in range(n):
            if color[v] != BLACK and M[u][v] != -1:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
    return res


for i in range(e):
    line = sys.stdin.readline()
    s, t, w = map(int, line.split())
    M[s][t] = w
    M[t][s] = w
print(prim())