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: Runtime Error

Solution code:

class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        # add the edge
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          # ??°????????????????????°
        #dist = [float('inf') for i in range(N)] # ?§????????????????????????§??????????????¢???????´???????
        dist = {k:float('inf') for k in self.nodes}
        #prev = [float('inf') for i in range(N)]

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)
            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:# and not(k in visited):
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    #prev[k]=mini

        return dist

    def prim(self):
        import heapq

        nodes=list(self.nodes.keys())
        N=len(nodes)

        X=[nodes[0]]
        unused=[]
        for u in self.adj[X[0]]:
            heapq.heappush(unused,(u,self.adj[X[0]][u]))

        total_cost=0
        while True:
            v,cost=heapq.heappop(unused)

            X.append(v)
            total_cost+=cost
            if len(X)==N:
                break

            for u in self.adj[v]:
                heapq.heappush(unused,(u,self.adj[v][u]))



        return total_cost




    def show(self):

        import networkx as nx
        import matplotlib.pyplot as plt
        G=nx.Graph()

        for e in self.edges:

            G.add_edge(e.node_from,e.node_to,weight=e.cost)
            #print(e.node_from,e.node_to,e.cost)

        pos=nx.spring_layout(G)
        #nx.draw_networkx_edges(G,pos=pos,edgelist=G.edges())
        edge_weight=dict([((u,v,),int(d['weight'])) for u,v,d in G.edges(data=True)])

        nx.draw_networkx_edge_labels(G,pos,edge_labels=edge_weight)
        #nx.draw_networkx_labels(G, pos)
        nx.draw_networkx_nodes(G,pos)
        nx.draw_networkx_edges(G,pos)
        nx.draw_networkx_labels(G,pos)
        #plt.axis('off')
        #nx.draw(G,with_labels=True)
        plt.show()



def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    a=spaceinput()
    g=myGraph()


    for i in range(999):
        ss=spaceinput()
        if not ss:
            break

        g.add_edge((ss[0],ss[1]),ss[2])

    print(g.prim())

    '''
    d=g.dijkstra(1)
    '''



    '''
    mint=10*9
    for k in range(1,n+1):
        dd=g.dijkstra(k)
        v=max(dd.values())
        if mint>v:
            mint=v


    print(mint)
    '''

Submission status: Runtime Error

Solution code:
import array
import collections
import heapq

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

#Prim?????§??????0?????????????°???¨?????¨(minimum spanning tree????±???????)
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
    #2????????????????????????????????\?????¨????????¨??????
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # ?????????????????\?????????????????\??£???????????????????????????
    in_pq = array.array("B", (True for _ in range(max_v)))
    
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq = True
    return (pred, key)

max_v, max_e = map(int, input().split())
adjacent_list = collections.defaultdict(set)

for _ in range(max_e):
    s, t, w = map(int, input().split())
    adjacent_list[s].add(AdjacentVertex(t,w))
    adjacent_list[t].add(AdjacentVertex(s,w))

(_, key) = compute_mst_prim(max_v, adjacent_list)

print(sum(key.values()))

Submission status: Runtime Error

Solution code:
import array
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)
    # ????????????????????\?????????????????\??£???????????????????????????
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

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()))import array
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)
    # ????????????????????\?????????????????\??£???????????????????????????
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)

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()))

Submission status: Runtime Error

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

T = spanning_tree(G)

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

print(s)

Submission status: Runtime Error

Solution code:
mport 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:
        val, u = heapq.heappop(hq)
        if val > d[u]:
            continue
        
        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: Runtime Error

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)