Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Minimum Spanning Tree

  For a given weighted graph $G = (V, E)$, find the minimum spanning tree (MST) of $G$ and print total weight of edges belong to the MST.

Input

  In the first line, an integer $n$ denoting the number of vertices in $G$ is given. In the following $n$ lines, a $n \times n$ adjacency matrix $A$ which represents $G$ is given.
$a_{ij}$ denotes the weight of edge connecting vertex $i$ and vertex $j$. If there is no edge between $i$ and $j$, $a_{ij}$ is given by -1.

Output

Print the total weight of the minimum spanning tree of $G$.

Constraints

$1 \leq n \leq 100$

$0 \leq a_{ij} \leq 2,000$ (if $a_{ij} \neq -1$)

$a_{ij} = a_{ji}$

$G$ is a connected graph

Sample Input 1

5
 -1 2 3 1 -1
 2 -1 -1 4 -1
 3 -1 -1 1 1
 1 4 1 -1 3
 -1 -1 1 3 -1

Sample Output 1

5

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
5
 -1 2 3 1 -1
 2 -1 -1 4 -1
 3 -1 -1 1 1
 1 4 1 -1 3
 -1 -1 1 3 -1


Sample output:
5

Submission status: Accepted

Solution code:
from sys import stdin
INF = 1<<21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1: M[i][j] = e
d = [INF] * n
d[0] = 0
color = [0] * n
def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = BLACK
        for v in range(0, n):
            if color[v] != BLACK and d[v] > M[u][v]:
                d[v] = M[u][v]
    return sum(d)
print(prim())

Submission status: Accepted

Solution code:
from sys import stdin
INF = float('inf')
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1: M[i][j] = e
d = [INF] * n
d[0] = 0
color = [0] * n
def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = BLACK
        for v in range(0, n):
            if color[v] != BLACK and d[v] > M[u][v]:
                d[v] = M[u][v]
    return sum(d)
print(prim())

Submission status: Accepted

Solution code:
from sys import stdin
INF = 1<<21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1: M[i][j] = e
d = [INF] * n
d[0] = 0
color = [False] * n
def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != True:
                u = i
                minv = d[i]
        if u == -1: break
        color[u] = True
        for v in range(0, n):
            if color[v] != True and d[v] > M[u][v]:
                d[v] = M[u][v]
    return sum(d)
print(prim())

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().strip())

dist = {}

for i in xrange(0, n):
    array = map(int, sys.stdin.readline().strip().split(" "))
    for (j, d) in enumerate(array):
        dist[(i, j)] = d

searched = []
length = 0

target = 0

while len(searched) != n:
    searched.append(target)
    min_len = 2001
    for v in searched:
        for i in xrange(0, n):
            if (i not in searched) and (min_len > dist[(v, i)]) and (dist[(v, i)] != -1):
                min_len = dist[(v, i)]
                target = i
    if min_len != 2001:
        length += min_len

print str(length)

Submission status: Accepted

Solution code:
n = int(raw_input())
matrix = []
for i in range(n):
    line = raw_input()
    splited = line.split()
    splited = map(lambda x: int(x), splited)
    matrix.append(splited)

result = 0
candidate = 0
selected = [0]
for i in range(n):
    weight = 2001
    for item in selected:
        for j in range(n):
            if matrix[j][item] != -1 and matrix[j][item] < weight and j not in selected:
                candidate = j
                weight = matrix[j][item]
    selected.append(candidate)
    if(len(selected) == n + 1):
        break
    result += weight
print result

Submission status: Accepted

Solution code:
import sys
from operator import add

n = int(sys.stdin.readline().strip())
A = [ [0] for i in range(n)]
for i in range(n):
	temp = map(int ,sys.stdin.readline().strip().split(" "))
	A[i] = temp


weight = [None for i in range(n)]
mitayatu=[False for i in range(n)]

def min(array):
	temp = 100000
	index= 0
	for i in range(n):
		if array[i] is not None and mitayatu[i]==False:
			if temp>=array[i]:
				temp = array[i]
				index = i
	return index

def owari():
	for i in mitayatu:
		if i is False:
			return False
	return True
# zero origin
def prim(nodeid):
	#print(nodeid)
	if owari() == True:
		return
	if mitayatu[nodeid]==True:
		return
	mitayatu[nodeid]=True
	for i in range(n):
		if A[nodeid][i]!=-1:
			if weight[i] is None:
				weight[i]=A[nodeid][i]
			elif weight[i]>A[nodeid][i] and mitayatu[i]==False:
				weight[i]=A[nodeid][i]
	prim(min(weight))

weight[0]=0
prim(0)

#print(weight)
print(reduce(add, weight))

Submission status: Accepted

Solution code:
import array
import collections
import heapq

INF = 1e9

N = int(input())

AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')
adjacency_list = collections.defaultdict(set)

NO_VERTEX = -1
 
def compute_mst_prim(max_v, adj_list):
    pred = collections.defaultdict(lambda: NO_VERTEX)
    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)

for i in range(N):
    u = list(map(int, input().split()))
    for j in range(N):
        if u[j] == -1:
            adjacency_list[i].add(AdjacentVertex(j, INF))
            adjacency_list[j].add(AdjacentVertex(i, INF))
        else:
            adjacency_list[i].add(AdjacentVertex(j, u[j]))
            adjacency_list[j].add(AdjacentVertex(i, u[j]))

(_, key) = compute_mst_prim(N, adjacency_list)

print(sum(key.values()))

Submission status: Accepted

Solution code:
INF = 1e9

n = int(input())
adj_matrix = [list(map(int, input().split())) for i in range(n)]


def prim(x):
    isVisited = [False] * x
    d = [INF] * x 
    d[0] = 0
    p = [-1] * x 
    
    while True:
        min_cost = INF
        
        for i in range(x):
            if isVisited[i] != True and d[i] < min_cost:
                min_cost = d[i]
                u = i
        
        if min_cost == INF:
            break
        
        isVisited[u] = True
        
        for v in range(x):
            if isVisited[v] != True and adj_matrix[u][v] != -1:
                if adj_matrix[u][v] < d[v]:
                    d[v] = adj_matrix[u][v]
                    p[v] = u
    return sum(d)

print(prim(n))

Submission status: Accepted

Solution code:
n = int(raw_input())
a = []
for i in range(n):
    a.append(map(int, raw_input().split()))
def prim(a):
    color = ['white' for i in range(n)]
    d = [10**9 for i in range(n)]
    p = [-1 for i in range(n)]
    d[0] = 0
    while True:
        mincost = 10**9
        for i in range(n):
            if color[i] != 'black' and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == 10**9:
            break
        color[u] = 'black'
        for v in range(n):
            if color[v] != 'black' and a[u][v] != -1:
                if a[u][v] < d[v]:
                    d[v] = a[u][v]
                    p[v] = u
                    color[v] = 'gray'
    print sum(d)
prim(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product

N = int(input())
INF = float("inf")
adj = []

for _ in range(N):
    adj.append([int(n) if n != "-1" else float("inf") for n in input().split()])

not_MST = list(range(1, N))
MST = [0]

cost = 0
while len(not_MST):
    tmp_min = INF
    tmp_idx = -1
    for m, n in product(MST, not_MST):
        if adj[m][n] < tmp_min:
            tmp_min = adj[m][n]
            tmp_idx = n
    MST.append(tmp_idx)
    not_MST.remove(tmp_idx)
    cost += tmp_min

print(cost)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def prim(G):
    n = len(G)
    heap = []
    s = 0
    for v, c in G[s].items():
        heappush(heap, (c, v))
    added = set()
    added.add(s)
    cost = 0
    while len(added) < n:
        cu, u = heappop(heap)
        if u in added:
            continue
        added.add(u)
        cost += cu
        for v, c in G[u].items():
            if v in added:
                continue
            heappush(heap, (c, v))
    return cost

n = int(raw_input())
G = {}
for i in range(n):
    if i not in G:
        G[i] = {}
    row = map(int, raw_input().strip().split(' '))
    for j in range(n):
        if row[j] == -1:
            continue
        G[i][j] = row[j]
        if j not in G:
            G[j] = {}
        G[j][i] = row[j]


cost = prim(G)
print cost

Submission status: Accepted

Solution code:
v = int(input())
G= [[int(i) for i in input().split()] for i in range(v)]
        
def prim(G, v):
    Vn = set([1])
    En = set([])
    V = set(range(1, v+1))
    while Vn != V:
        m = float('inf')
        for u in Vn:
            for v in V - Vn:
                if G[u - 1][v - 1] == -1:continue
                if G[u - 1][v - 1] < m:
                    m = G[u - 1][v -1]
                    k = (u,v)
        Vn.add(k[1])
        En.add(k)
    return En

print(sum(G[u - 1][v -1] for u,v in prim(G, v)))

Submission status: Accepted

Solution code:
n = int(input())
G = [[int(i) for i in input().split()] for i in range(n)]

S = set([])
for i,row in enumerate(G):
    for j,col in enumerate(row):
        if col != -1:
            k = tuple(sorted([i,j]))
            S.add(k + (col, ))

rank = {}
p = {}

def makeSet(x):
    p[x] = x
    rank[x] = 0

def link(x, y):
    if  rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
    if  rank[x] == rank[y]:
        rank[y] += 1

def union(x, y):
    link(findSet(x), findSet(y))
    
def findSet(x):
    if  x != p[x]:
        p[x] = findSet(p[x])
    return p[x]
    
def isSameSet(x, y):
    return findSet(x) == findSet(y)

def kruskal(G, n, S):
    ret = 0
    for x in range(n):
        makeSet(x)
    while len(S) != 0:
        u, v, c = min(S, key=lambda x: x[2])
        S = S - set([(u,v,c)])
        if not isSameSet(u, v):
            union(u, v)
            ret += c
    return ret
print(kruskal(G, n, S))

Submission status: Accepted

Solution code:
def main():
    n = input()
    A = []
    for i in xrange(n):
        A.append(map(int,raw_input().split()))

    inf = float('inf')
    d = [inf]*n
    p = [-1]*n
    c = [-1]*n
    d[0] = 0

    while(True):
        mincost = inf
        for i in xrange(n):
            if(c[i] != 1) & (d[i] < mincost):
                mincost = d[i]
                u = i
        if mincost == inf:
            break

        c[u] = 1
        
        for v in xrange(n):
            if (c[v] != 1) & (A[u][v] != -1):
                if A[u][v] < d[v]:
                    d[v] = A[u][v]
                    p[v] = u
                    c[v] = 0

    cost = 0
    for i in xrange(n):
        if(p[i] != -1):
            cost += A[i][p[i]]

    print cost
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
v_num = int(input())
edges = defaultdict(list)
for i in range(v_num):
    data = [int(n) for n in input().split(" ")[1:]]
    for j in range(i + 1, v_num):
        if data[j] != -1:
            edges[i].append([data[j], j])
            edges[j].append([data[j], i])
queue = []
heapq.heapify(queue)
for c in edges[0]:
    heapq.heappush(queue, c)
visited = {0}
answer = 0
while len(visited) < v_num:
    q = heapq.heappop(queue)
    weight, one = q[0], q[1]
    if one in visited:
        continue
    answer += weight
    for e in edges[one]:
        heapq.heappush(queue, e)
    visited |= {one}
print(answer)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
v_num = int(input())
edges = defaultdict(list)
for i in range(v_num):
    data = [int(n) for n in input().split(" ")[1:]]
    for j in range(i + 1, v_num):
        if data[j] != -1:
            edges[i].append([data[j], j])
            edges[j].append([data[j], i])
queue = []
heapq.heapify(queue)
for c in edges[0]:
    heapq.heappush(queue, c)
visited = {0}
answer = 0
while len(visited) < v_num:
    q = heapq.heappop(queue)
    weight, one = q[0], q[1]
    if one in visited:
        continue
    answer += weight
    for e in edges[one]:
        if e[1] not in visited:
            heapq.heappush(queue, e)
    visited |= {one}
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = []

for i in range(n):
    inp = input()
    if "-1" in inp:
        inp = inp.replace("-1","10000")
    a.append(list(map(int, inp.split())))

w = 0
v = set()
v.add(0)

while len(v) < n:
    min_w   = 10000
    min_idx = 0
    i = 0
    for node in v:
        if min_w > min(a[node]):
            min_w = min(a[node])
            i = node
            min_idx = a[i].index(min_w)
    if min_idx in v:
        a[i][min_idx] = 10000
        continue
    else:
        w += min_w
        v.add(min_idx)

print(w)

Submission status: Accepted

Solution code:
n = int(input())
edgeArray = [list(map(int, input().split())) for i in range(n)]
edgeList = []
rootList = [-1 for i in range(n)]
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        
for i in range(n):
    for j in range(i):
        if edgeArray[i][j] != -1:
            edgeList.append([edgeArray[i][j], i, j])
edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Submission status: Accepted

Solution code:
n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], i, j])
rootList = [-1 for i in range(n)]
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        

edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Submission status: Accepted

Solution code:
n = int(input())
edgeList = []
rootList = [-1 for i in range(n)]

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], getRoot(i), getRoot(j)])
sumLength = 0
edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Submission status: Accepted

Solution code:
n = int(input())
edgeList = []
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(i):
        if a[j] != -1:
            edgeList.append([a[j], i, j])
rootList = [-1]*n
sumLength = 0

def getRoot(x):
    r = rootList[x]
    if r < 0:
        rootList[x] = x
    elif r != x:
        rootList[x] = getRoot(r)
    return rootList[x]
        

edgeList.sort(key=lambda x: x[0])
for e in edgeList:
    x = getRoot(e[1])
    y = getRoot(e[2])
    if x != y:
        sumLength += e[0]
        rootList[x] = rootList[y] = min(x, y)
print(sumLength)

Submission status: Accepted

Solution code:
INFTY = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2

n = int(input())
M = [list(map(int, input().split())) for i in range(n)]

d = [INFTY for i in range(n)]
p = [-1 for i in range(n)]
color = [WHITE for i in range(n)]

for i in range(n):
    for j in range(n):
        if (M[i][j] == -1):
            M[i][j] = INFTY

def prim():
    global M, d, p, color
    d[0] = 0
    while(1):
        minv = INFTY
        u = -1
        for i in range(n):
            if (minv > d[i] and color[i] != BLACK):
                u = i
                minv = d[i]
        if (u == -1):
            break
        color[u] = BLACK
        for v in range(n):
            if (color[v] != BLACK and M[u][v] != INFTY):
                if (d[v] > M[u][v]):
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = GRAY
    
    return sum([M[i][p[i]] for i in range(n) if p[i] != -1])

print(prim())

Submission status: Accepted

Solution code:
inf = float('inf')
n = int(input())
a = []

for i in range(n):
    line = list(map(int, input().split()))
    for i in range(len(line)):
        if line[i] == -1:
            # infinity weight if not connected
            line[i] = inf
    a.append(line)

checked = [False] * n
d = [inf] * n
checked[0] = True
ans = 0
nxt = 0

for i in range(n - 1):
    for j in range(n):
        if a[nxt][j] < d[j]:
            d[j] = a[nxt][j]

    min_n = 0
    min_w = inf

    for j in range(n):
        if not checked[j] and d[j] < min_w:
            min_n = j
            min_w = d[j]

    checked[min_n] = True
    nxt = min_n
    ans += min_w

print(ans)

Submission status: Accepted

Solution code:
import itertools

n = int(input())
A = []
for i in range(n):
    line = input()
    A.append([int(x) for x in line.split()])


V = set(range(n))
Vnew = {0}  # ??¨???????°???¨?????????
weights = []

while V != Vnew:
    T = V - Vnew
    minw = float('inf')
    for u, v in itertools.product(Vnew, T):
        w = A[u][v]
        if w != -1 and minw > w:
            e = (u, v)
            minw = w
    Vnew.add(e[1])
    weights.append(minw)

print(sum(weights))

Submission status: Accepted

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


if __name__ == '__main__':

    n = int(input())
    M = [list(map(int, input().split(" ")[1:])) for _ in range(n)]

    color = [0] * n
    d = [float("inf")] * n
    p = [None] * n

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

        while True:
            mincost = float("inf")
            for i in range(n):
                if color[i] != 2 and d[i] < mincost:
                    mincost = d[i]
                    u = i

            if mincost == float("inf"):
                break

            color[u] = 2

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

    prim()
    sum = 0
    for i in range(n):
        if p[i] != -1:
            sum += M[i][p[i]]

    print(sum)

Submission status: Accepted

Solution code:
INF = float("inf")
def MAIN():
    n = int(input())
    M = [[INF] * 101 for _ in range(101)]
    for i in range(n):
        for j, e in enumerate(map(int, input().split())):
            if e != -1:
                M[i][j] = e
    def prim():
        d = [INF] * n
        t = [-1] * n
        color = [0] * n
        d[0] = 0
        while True:
            minv = 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 v in range(n):
                if color[v] != 2 and d[v] > M[u][v]:
                    d[v] = M[u][v]
                    t[v] = u
                    color[v] = 1
        return sum(d)
    print(prim())
MAIN()

Submission status: Accepted

Solution code:
n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*~-n
p=[-1]*n
b=[1]*n
while 1:
 m,u=1e4,-1
 for i in range(n):
  if m>d[i]and b[i]:m,u=d[i],i
 if u<0:break
 b[u]=0
 for v in range(n):
  if b[v]and 1+M[u][v]and d[v]>M[u][v]:
   d[v],p[v]=M[u][v],u
print(sum(M[i][p[i]]for i in range(n)if p[i]+1))

Submission status: Accepted

Solution code:
n=int(input())
M=[list(map(int,input().split()))for _ in[0]*n]
d=[0]+[1e4]*~-n
b=[1]*n
a=0
while 1:
 u=-1
 for i in range(n):
  if b[i]and(u<0 or d[i]<d[u]):u=i
 if u<0:break
 b[u]=0
 a+=d[u]
 for v in range(n):
  t=M[u][v]
  if t+1 and d[v]>t:d[v]=t
print(a)

Submission status: Accepted

Solution code:
n=int(input())
edgeList=[]
for i in range(n):
 a=list(map(int,input().split()))
 for j in range(i):
  if a[j]>=0:edgeList+=[(a[j],i,j)]
rootList=[-1]*n
sumLength=0
def getRoot(x):
 r=rootList[x]
 if r<0:rootList[x]=x
 elif r!=x:rootList[x]=getRoot(r)
 return rootList[x]
edgeList.sort(key=lambda x:x[0])
for e in edgeList:
 x=getRoot(e[1])
 y=getRoot(e[2])
 if x!=y:
  sumLength+=e[0]
  rootList[x]=rootList[y]=min(x,y)
print(sumLength)

Submission status: Accepted

Solution code:
n = int(input())

a = []
for i in range(n):
    a.append(list(map(int, input().split())))

ans = 0
mincost = [2001] * n
flag = [0] * n
mincost[0] = 0

while 1:
    v = -1
    for j in range(n):
        if flag[j] != 1 and (v == -1 or mincost[j] < mincost[v]):
            v = j
    if v == -1:
        break
    flag[v] = 1
    ans += mincost[v]
    for j in range(n):
        if a[v][j] == -1:
            continue
        mincost[j] = min(mincost[j], a[v][j])
print(ans)

Submission status: Accepted

Solution code:
INF = 1e9

n = int(input())

a = []
for i in range(n):
    a.append(list(map(int, input().split())))

def prim(n):
    flag = [0] * n
    d = [INF] * n
    d[0] = 0
    p = [-1] * n

    while True:
        min_cost = INF
        
        for i in range(n):
            if flag[i] != 1 and d[i] < min_cost:
                min_cost = d[i]
                u = i
        if min_cost == INF:
            break
        flag[u] = 1
        
        for v in range(n):
            if flag[v] != 1 and a[u][v] != -1:
                if a[u][v] < d[v]:
                    d[v] = a[u][v]
                    p[v] = u
    return sum(d)

print(prim(n))

Submission status: Accepted

Solution code:
from enum import Enum, auto
class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

n = int(input())
M = []
for i in range(n):
    arr = [int(x) for x in input().split(' ') if x != '']
    M.append(arr)
colors = []
d = []
p = [0 for i in range(n)]

INFTY = 2001
def prim():
    global d
    colors = [Color.WHITE for i in range(n)]
    d = [INFTY for i in range(n)]

    d[0] = 0 # iに入る辺の重み **最小全域木は (頂点の数)-1 = (辺の数)
    p[0] = -1 # 0を根にする

    while True:
        mincost = INFTY
        u = 0
        for i in range(n):
            if colors[i] != Color.BLACK and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == INFTY: break

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

prim()
print(sum(d))

Submission status: Accepted

Solution code:
import heapq


class MST:
    """Given weighted graph, find minimum spanning tree.

    >>> mst = MST([[-1, 2, 3, 1, -1], \
                   [2, -1, -1, 4, -1], \
                   [3, -1, -1, 1, 1], \
                   [1, 4, 1, -1, 3], \
                   [-1, -1, 1, 3, -1]]);
    >>> mst.weight()
    5
    """
    MAX_WEIGHT = 2001

    def __init__(self, graph):
        self.graph = graph
        self.size = len(graph)
        self.tree = []
        self._search()

    def weight(self):
        return sum([self.graph[i][j] for i, j in self.tree])

    def _search(self):
        visited = [0]

        while len(visited) < self.size:
            h = []
            for node in visited:
                for i, w in enumerate(self.graph[node]):
                    if w == -1:
                        continue
                    if i in visited:
                        continue
                    heapq.heappush(h, (w, node, i))

            weight, src, dst = heapq.heappop(h)
            visited.append(dst)
            self.tree.append((src, dst))


def run():
    n = int(input())

    nodes = []
    for _ in range(n):
        nodes.append([int(i) for i in input().split()])

    mst = MST(nodes)
    print(mst.weight())


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
n = int(input())
sides = []
ws = []
ss = []
for _ in range(n):
    sides.append(list(map(int,input().split())))
for i in range(n):
    for j in range(i+1,n):
        if sides[i][j] >= 0:
            ws.append([sides[i][j],i,j])
rs = [(i) for i in range(n)]
def root(x):
    global rs
    if rs[x] == x:
        return(x)
    else:
        return(root(rs[x]))
ws.sort()
ans = 0
while(len(ws)):
    if root(ws[0][1]) != root(ws[0][2]):
        ans += ws[0][0]
        rs[root(rs[ws[0][2]])] = root(ws[0][1])
        ss.append(ws[0])
    del(ws[0])
print(ans)

Submission status: Accepted

Solution code:
import sys
INF = float('inf')
n = int(input())
adja_matrix = [[int(i) for i in line.split()] for line in sys.stdin.read().splitlines()]
condition = ['INIT'] * n
distance = [INF] * n
p = [0] * n
distance[0] = 0
p[0] = -1

while True:
    mincost = INF
    for i in range(n):
        if condition[i] != 'FINISH' and distance[i] < mincost:
            mincost = distance[i]
            u = i

    if mincost == INF:
        break

    condition[u] = 'FINISH'

    for v in range(n):
        if condition[v] != 'FINISH' and adja_matrix[u][v] != -1:
            if adja_matrix[u][v] < distance[v]:
                distance[v] = adja_matrix[u][v]
                p[v] = u
                condition[v] = 'CHECK'

sum = 0
for i in range(n):
    if p[i] != -1:
        sum += adja_matrix[i][p[i]]

print(sum)

Submission status: Accepted

Solution code:
n = int(input())
m = []

for _ in range(n):
    tmp = [int(x) for x in input().split()]
    m.append(tmp)

#辺を全て持つリストを作る
edge_list = [] 
j = 1
for i in range(n-1):
    for k,x in enumerate(m[i][j:]):
        if x != -1:
            edge_list.append((x,i,k+j))
        else:
            pass
    j += 1
edge_list.sort()

root_list = [i for i in range(n)]

def root(x):
    path_to_root = []
    while root_list[x] != x:
        path_to_root.append(x)
        x = root_list[x]
    for node in path_to_root:
        root_list[node] = x
    return x

def is_same_root(x,y):
    return root(x) == root(y)

def unite(x,y):
    root_list[root(x)] = root(y)

cost = 0
for x in edge_list:
    w,p,q = x
    if is_same_root(p,q):
        continue
    else:
        cost += w
        unite(p,q)

print(cost)

Submission status: Accepted

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


# Union find
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = list(range(N))

    def root(self, x):
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        groups = {}
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result


# Kruscal法: 最小全域木
# num_vertices: int
# edges=(vertex1, vertex2, weight): List[int, int, int]
# edgesについて破壊的
def kruskal(num_vertices, edges):
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


n = int(input())
edges = []
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(i, n):
        if row[j] != -1:
            edges.append([i, j, row[j]])
print(kruskal(n, edges))

Submission status: Accepted

Solution code:
n = int(input())

INF = 2147483647
G = [[INF for j in range(n)] for i in range(n+1)]
check = [0 for i in range(n)]


def prim():
    d = [INF for i in range(n)]
    p = [-1 for i in range(n)]
    d[0] = 0
    cost = 0

    while True:
        min_cost = INF
        for i in range(n):
            if check[i] != 2 and d[i] < min_cost:
                min_cost = d[i]
                u = i

        if min_cost == INF:
            break

        cost += d[u]
        check[u] = 2

        for v in range(n):
            if check[v] != 2 and G[u][v] != INF:
                if G[u][v] < d[v]:
                    d[v] = G[u][v]
                    p[v] = u
                    check[v] = 1

    return cost


def main():
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            if data[j] != -1:
                G[i][j] = data[j]

    print(prim())


if __name__ == '__main__':
    main()