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:
class UnionFindTree:
    """
        Disjoint set data structure
        Union-Find tree
        complexity:
            init: O(n)
            find, unite, same: O(alpha(n))
    """
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n

    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 unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        elif 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 same(self, x, y):
        return self.find(x) == self.find(y)


class Kruskal:
    """
        Kruskal's algorithm: find Minimum Spanning Tree
        complexity:
            O(E logV)
    """
    def __init__(self, V, E, start=0, INF=10**9):
        """
        :param V: the number of vertices
        :param E:  adjacency list (undirected graph)
        :param start:
        :param INF:
        """
        self.kruskal(V, E)

    def kruskal(self, V, E):
        edges = []
        for v1 in range(V):
            for v2, cost in E[v1]:
                if v1 < v2:
                    edges.append((cost, v1, v2))
        edges.sort(reverse=True)
        self.mincost = 0
        self.min_spanning_tree = []
        uf = UnionFindTree(V)
        while len(self.min_spanning_tree) < V - 1:
            cost, v1, v2 = edges.pop()
            if not uf.same(v1, v2):
                self.mincost += cost
                uf.unite(v1, v2)
                self.min_spanning_tree.append((v1, v2, cost))

    def min_cost(self):
        return self.mincost

    def get_min_spanning_tree(self):
        return sorted(self.min_spanning_tree)


V = int(input())
edges = [[] for _ in range(V)]
for i in range(V):
    for j, d in enumerate(map(int, input().split())):
        if d != -1:
            edges[i].append((j, d))
mst = Kruskal(V, edges)
print(mst.min_cost())

Submission status: Accepted

Solution code:
#coding:utf-8
inf = 1000000
n = int(input())
mtrx = []
for i in range(n):
    nums = list(map(int,input().split()))
    col = []
    for j in range(n):
        if nums[j] == -1:
            col.append(inf)
        else:
            col.append(nums[j])
    mtrx.append(col)

        
d = [inf for i in range(n)]
p = [-1 for i in range(n)]
color = ["white" for i in range(n)]
d[0] = 0
while True:
    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 mtrx[u][v] < inf:
            if mtrx[u][v] < d[v]:
                d[v] = mtrx[u][v]
                p[v] = u
                color[v] = "gray"
print(sum(d))

Submission status: Accepted

Solution code:
import sys
    
global status, d
status = {}
d=0

def mst(p1, GRAPH):
    global status
    
    edge={}
    total = 0
    mini = 0
    while True:
        status[p1]=True
        for p2 in range(len(status)):
            if status[p2]==False and GRAPH.has_key((p1,p2)):
                edge[(p1, p2)]=GRAPH[(p1, p2)]
        mini=1000000
        for key, value in edge.items():
            if status[key[1]]==True:
                del edge[key]
                continue
            if value <mini:
                key0 = key
                mini = value
        if mini!=1000000:
            total+=mini
            p1=key0[1]
        else:
            break
    
    return total

n = int(raw_input())
x = {}
for i in range(n):
    seq = map(int,raw_input().split())
    for j in range(n):
        tmp = seq[j]
        if tmp != -1:
            x[(i, j)]=tmp
    status[i] = False

print mst(0, x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    M = []
    for _ in xrange(num):
        M.append([int(s) for s in stdin.readline().split()])

    g = set(xrange(1, num+1))
    index = g.pop()
    h = {index}
    gravity = 0

    while g:
        minimum = maxint
        for j in h:
            mj = M[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]
        h.add(index)
        g.remove(index)
        gravity += minimum

    print(gravity)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    M = []
    for _ in xrange(num):
        M.append([int(s) for s in stdin.readline().split()])

    g = set(xrange(1, num+1))
    index = g.pop()
    h = {index}
    weight = 0

    while g:
        minimum = maxint
        for j in h:
            mj = M[j-1]
            for i in g:
                if 0 <= mj[i-1] < minimum:
                    index = i
                    minimum = mj[i-1]
        h.add(index)
        g.remove(index)
        weight += minimum

    print(weight)


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify

n = int(input())
g = [[] for _ in range(n)]

for i in range(n):
    for j,k in enumerate(map(int,input().split())):
        if k != -1:
            g[i].append((j,k))
#    print(g[i])

ocupied = [0]*n
que = [(j,k) for k,j in g[0]] # 重み、子の順番
#print(f'g[0]: {g[0]}')　#子、重みの順番
#print(f'que: {que}')
ocupied[0] = 1
heapify(que)

ans = 0
while que:
    cv,v = heappop(que)
    #print(f'cv, v: {cv}, {v}')
    if ocupied[v]: # vは頂点　どこでvが頂点になるか
        continue
    ocupied[v] = 1
    ans += cv
    for j,k in g[v]:
        if ocupied[j]:
            continue
        heappush(que,(k,j))
    #print(f'ocupied: {ocupied}')
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n: int):
        self.nodes = n
        self.parents = [-1] * n
        self.rank = [0] * n

    # retrun the root of element x
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # unite the group include element x and group include element y
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # get size of the gourp which element x belongs
    def get_size(self, x):
        return -self.parents[self.find(x)]

    # check if element x and element y is same group
    def same(self, x, y):
        return self.find(x) == self.find(y)


def kruskal(n: int, edges: list):
    """
    n: count of nodes
    edges: list of edges, format: (node1,node2,weight)
    """
    union = UnionFind(n + 1)  # 1-indexed
    mst_sum = 0
    mst = []
    for edge in edges:
        n1, n2, w = edge
        if not union.same(n1, n2):
            union.unite(n1, n2)
            mst_sum += w
            mst.append(edge)
    return mst, mst_sum


n = int(input())
graph_table = []

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

edges = []
# edge一覧を取得
for i in range(n - 1):
    for j in range(i + 1, n):
        if graph_table[i][j] != -1:
            edges.append((i, j, graph_table[i][j]))  # node1,node2,weight

# edgeを重みの昇順にソート
edges = sorted(edges, key=lambda x: x[2])

_, mst_sum = kruskal(n, edges)
print(mst_sum)

Submission status: Accepted

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

import heapq

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

    while True:
        mincost = 3000
        for i in range(1, N+1):
            if color[i] != 2 and d[i] < mincost:
                mincost = d[i]
                u = i
        if mincost == 3000:
            break

        color[u] = 2

        for v in range(1, N+1):
            if color[v] != 2 and M[u][v] != 3000:
                if M[u][v] < d[v]:
                    d[v] = M[u][v]
                    p[v] = u
                    color[v] = 1
    
    sum_ = 0
    for i in range(1, N+1):
        if p[i] != -1:
            sum_ += M[i][p[i]]

    return sum_




N = int(input())
color = [0] * (N+1)
counter = 0
d = [3000] * (N+1) #V-T間の重み最小辺の記録
p = [-1] * (N+1)
M = [[3000] * (N+1) for i in range(N+1)]

for i in range(1, N+1):
    A = list(map(int, input().split()))
    for j, v in enumerate(A):
        if v != -1:
            M[i][j+1] = v

print(prim(N))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    uf = UnionFind(N)
    ret = 0
    cost = []
    for i in range(N):
        D = il()
        for j in range(N):
            if D[j] != -1:
                cost.append((D[j], i, j))
    else:
        cost.sort()
        for c, v1, v2 in cost:
            if not uf.same(v1, v2):
                ret += c
                uf.unite(v1, v2)
        print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
INFTY = 10**5
WHITE = 0
GRAY = 1
BLACK = 2

A = [[ int(row) if row != "-1" else INFTY for row in input().split()] for i in range(n)]

def prim(A, st):
    colors = [WHITE] * n
    colors[st] = BLACK
    T = [st]
    total_weights = 0
    
    while len(T) < n:
    
        current_min = INFTY
        next_add = st
        for node_inT in T:
            for v in range(n):
                if colors[v] == WHITE and A[node_inT][v] < current_min:
                    current_min = A[node_inT][v]
                    next_add = v

        total_weights += current_min
        T.append(next_add)
        colors[next_add] = BLACK
    
    return total_weights

MST = [0] * n
for i in range(n):
    MST[i] = prim(A, i)

print(min(MST))

Submission status: Accepted

Solution code:
def prim():
    visited = [0]*n
    d = [float("inf")]*n
    p = [-1]*n
    
    d[0] = 0

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

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

        visited[u] = 2

        for v in range(n):
            if visited[v] != 2 and M[u][v] != float("inf"):
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u
                    visited[v] = 1
                
    ans = 0
    for i,j in enumerate(p[1:], start=1):
        ans += M[i][j]
        
    return ans


n = int(input())
M = []

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


print(prim())

Submission status: Accepted

Solution code:
n=int(input())
inf=10000
color=["white" for i in range(n)]
p=[-1 for i in range(n)]
d=[inf for i in range(n)]
M=[[] for i in range(n)]


for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(n):
        if tmp[j]==-1:
            M[i].append(inf)
        else:
            M[i].append(tmp[j])

def prim():
    d[0]=0
    while True:
        mincost=inf
        for i in range(n):
            if mincost>d[i] and color[i]!="black":
                mincost=d[i]
                u=i
        if mincost==inf:
            break
        color[u]="black"
        for j in range(n):
            if color[j]!="black" and M[u][j]!=inf:
                if M[u][j]<d[j]:
                    d[j]=M[u][j]
                    p[j]=u
                    color[j]="gray"

prim()
print(sum(d))

Submission status: Accepted

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]

isVisited = [False] * n
d = [0] + [2001] * (n - 1)
p = [-1] * n

while True:
    mincost = 2001
    for i in range(n):
        if (not isVisited[i]) and (d[i] < mincost):
            mincost = d[i]
            u = i

    if mincost == 2001:
        break

    isVisited[u] = True

    for v in range(n):
        if (not isVisited[v]) and (A[u][v] != -1): #uと繋がる頂点v
            if A[u][v] < d[v]:
                d[v] = A[u][v]
                p[v] = u

print(sum(d))

Submission status: Accepted

Solution code:
def prim(n,M):
    d = [None]*n
    p = [None]*n
    searched = [0]*n
    
    for i in range(n):
        d[i] = float("inf")
        p[i] = -1
    
    d[0] = 0
    
    while True:
        minv = float("inf")
        u = -1
        for i in range(n):
            if minv > d[i] and not searched[i]:
                u = i
                minv = d[i]
        
        if u == -1:
            break
        searched[u] = 1
        for v in range(n):
            if (not searched[v]) and M[u][v] != -1:
                if d[v] > M[u][v]:
                    d[v] = M[u][v]
                    p[v] = u

    s = 0
    for i in range(n):
        if p[i] != -1:
            s += M[i][p[i]]
    return print(s)

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

Submission status: Accepted

Solution code:
def prim(n, cost):
    mincost = [float("inf")]*n
    used = [False] * n
    mincost[0] = 0
    res = 0
    cnt = 1
    while True:
        u = -1
        for i in range(n):
            if (not used[i]) and (u == -1 or mincost[i] < mincost[u]):
                u = i
        if u == -1:
            break
        used[u] = True
        res += mincost[u]
        for v in range(n):
            if cost[u][v] != -1:
                mincost[v] = min(mincost[v], cost[u][v])
    return res


def main():
    n = int(input())
    g = []
    for _ in range(n):
        g.append(list(map(int, input().split())))
    print(prim(n, g))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
P = [i for i in range(N)]
weight = []

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

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

def unite(x,y):
    P[root(x)] = root(y)
    
# まずは辺の重さをソートするために辺の重さの配列を作りましょう→マイナス1は除外
for i in range(N):
    lis = list(map(int,input().split()))
    for j in range(N):
        if lis[j] == -1:
            continue
        else:
            weight.append([lis[j],i,j])
# ソートされた順に小さい順から次々とuniteして行こう
weight.sort()
length = len(weight)
k = 0
total_weight = 0

for k in range(length):
    if is_same_set(weight[k][1],weight[k][2]):
        continue
    else:
        unite(weight[k][1],weight[k][2])
        total_weight += weight[k][0]

print(total_weight)
    
# その際にもし付け加えてis_same_set(x,y)がtrueだったらやめよう

Submission status: Accepted

Solution code:
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)
    
    

n= int(input())
a=[]
P=[i for i in range(n)]

for i in range(n):
    temp= list(map(int,input().split()))
    for j in range(i,n):
        if temp[j] != -1:
            a.append([temp[j], i, j])
a.sort()
ans=0
for i in a:
    if not(is_same_set(P[i[1]],P[i[2]])):
        unite(i[1],i[2])
        ans+= i[0]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

ds=[i for i in range(n)]
def root(x):
  path_to_root = []
  while ds[x] != x:
    path_to_root.append(x)
    x = ds[x]
  for i in path_to_root:
    ds[i] = x
  return x
def same(x,y):
  return root(x) == root(y)
def unite(x,y):
  ds[root(x)] = root(y)

p=[] #[a,i,j]:i<j
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(i+1,n):
    if a[j]!=-1: p.append([a[j],i,j])
p.sort(key=lambda x:x[0])
ans=0
for i in p:
  if same(i[1],i[2]): continue
  unite(i[1],i[2])
  ans+=i[0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

ep = []
for i in range (N):
    a = list(map(int,input().strip().split()))
    for j in range(i,N):
        if a[j] != -1:
            ep.append([a[j],i,j])

P = [i for i in range(N)]
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x # パス圧縮
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)

ep.sort()
T = []
ans = 0
for e in ep:
    if is_same_set(e[1],e[2]) == False:
        ans += e[0]
        unite(e[1],e[2])
print(ans)

Submission status: Accepted

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

tree = [i for i in range(n)]
def root(x):
    pre = []
    while x != tree[x]:
        pre.append(x)
        x = tree[x]
    for node in pre:
        tree[node] = x
    return x
def unite(x, y):
    X, Y = root(x), root(y)
    if X != Y:
        tree[X] = Y

for cost, x, y in edge:
    X, Y = root(x), root(y)
    if X != Y:
        ans += cost
        tree[X] = Y
print(ans)

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

def kruskal(es, V):
    es.sort(key=lambda x:x[2])
    uf = UnionFind(V)
    res = 0
    for e in es:
        if not uf.same(e[0], e[1]):
            uf.unite(e[0], e[1])
            res += e[2]
    return res

def resolve():
    n = I()
    es = []
    for i in range(n):
        a = LI()
        for j in range(n):
            if a[j]!=-1:
                es.append((i, j, a[j]))

    ans = kruskal(es, n)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

def readinput():
    n=int(input())
    nMat=[]
    for _ in range(n):
        m=list(map(int,input().split()))
        nMat.append(m)
    
    return n,nMat

WHITE=0
GRAY=1
BLACK=2
INFTY=sys.maxsize
def prim(n,nMat):

    color=[WHITE]*n
    d=[INFTY]*n
    p=[-1]*n

    d[0]=0
    p[0]=-1

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

        if mincost==INFTY:
            break

        # Tに属する頂点とV-Tに属する頂点をつなぐ辺の中で最小のコストのもの(u,p[u])が選ばれた
        color[u]=BLACK

        # V-Tに属する各頂点vとTに属する頂点をつなぐ辺の中で最小のコストのものが(v,p[v])でそのコストがd[v]
        # uがTに入ったことで辺(u,v)のコストとd[v]を比べてd[v]が大きかったらp[v]=u, d[v]=辺(u,v)のコストで更新
        for v in range(n):
            if color[v]!=BLACK and nMat[u][v]!=-1:
                if nMat[u][v]<d[v]:
                    d[v]=nMat[u][v]
                    p[v]=u
                    color[v]=GRAY
    return p,d


def main(n,nMat):
    p,d=prim(n,nMat)
    
    ans=0
    for i in range(n):
        if p[i] != -1:
            ans+=d[i]
    
    return ans

if __name__=='__main__':
    n,nMat=readinput()
    ans=main(n,nMat)
    print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import decimal
INF = 10**18
WHITE = 0
GRAY = 1
BLACK = 2

def Prim():
    d = [INF]*(n)
    c = [WHITE]*(n)
    p = [-1]*(n)

    d[0] = 0
    while True:
        minv = INF
        u = -1
        for i in range(n):
            if minv > d[i] and c[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1:
            break
        c[u] = BLACK
        for v in range(n):
            if c[v] != BLACK and G[u][v] != INF:
                if d[v] > G[u][v]:
                    d[v] = G[u][v]
                    p[v] = u
                    c[v] = GRAY
    sum_g = 0
    for i in range(n):
        if p[i] != -1:
            sum_g += G[i][p[i]]
    return sum_g


if __name__ == "__main__":
    n = int(input())
    G = []
    for i in range(n):
        s = list(map(int,input().split()))
        G.append(s)
    for i in range(n):
        for j in range(n):
            if G[i][j] == -1:
                G[i][j] = INF
    ans = Prim()
    print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq

def main():
    n = int(input())
    next = []
    for _ in range(n):
        l = list(map(int, input().split()))
        next.append([(c, i) for i, c in enumerate(l) if c != -1])
    visited = [0] * n
    connection = 0
    q = [(0, 0)]    # (cost, v)
    heapq.heapify(q)
    ans = 0
    while len(q):
        cost, v = heapq.heappop(q)
        if visited[v]:
            continue

        # そのノードと繋げる
        visited[v] = 1
        connection += 1
        ans += cost
        
        # 新たに繋げたノードから行けるところをエンキュー
        for i in next[v]:
            heapq.heappush(q, i)
        
        # 全部のノードが繋がったら終了
        if connection == n:
            break
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x=self.find_root(x)
        y=self.find_root(y)

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

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

    def cnt(self,x):
        return -self.root[self.find_root(x)]

n=int(input().rstrip())
G=union_find(n)
g=[]
for k in range(n):
    a=[int(i) for i in input().split()]
    for j in range(n):
        if a[j]!=-1:
            g.append((k,j,a[j]))
g.sort(key=lambda x:x[2])
ans=0
for i in g:
    u,v,c=i
    if not G.same(u,v):
        G.unite(u,v)
        ans+=c
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

#M[u][v]:uからvへの重みを保存した隣接行列
M=[]
for n in range(N):
    input_temp = list(map(int,input().split()))
    M.append(input_temp)

#color:各頂点の訪問状態を示す
color=['white']*N

#d:TとV-Tを繋ぐ辺の中で重みが最小の辺の重みの値を保持
d=[10**10]*N

#p[v-1]:MSTにおけるvの親を保持
p=[-1]*N

#初期値
d[0] = 0
p[0] = -1

# ans=0
while True:
#     ans+=1
    mincost=10**10
    for i in range(N):
        if color[i] != 'BLACK' and d[i] < mincost:
            mincost = d[i]
            u = i
#     print(u,mincost)       
    if mincost == 10**10:
        break
    
    color[u] = 'BLACK'
    
    for v in range(N):
        if color[v] != 'BLACK' and M[u][v]!=-1:
#             print(u,v,color[v],M[u][v],d[v])
            if M[u][v] < d[v]:
                d[v] = M[u][v]
                p[v] = u
                color[v] = 'GRAY'
#     print(color,mincost,d,p)
    
print(sum(d))

Submission status: Accepted

Solution code:
N=int(input())
graph=[]
d=[2000]*(N)
p=[None]*(N)
color=["white"]*(N+1)
for i in range(N):
    a=list(map(int,input().split()))
    graph.append(a)
def prim():
    d[0]=0
    p[0]=-1
    while (True):
        mincost=2000
        for i in range(N):
            if color[i]!="black" and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==2000:break
        color[u]="black"
        for v in range(N):
            if color[v]!="black" and graph[u][v]!=-1:
                if graph[u][v]<d[v]:
                    d[v]=graph[u][v]
                    p[v]=u
                    color[v]="gray"
prim()
print(sum(d))

Submission status: Accepted

Solution code:
import heapq

def make_adj_list(v):
    adj_list = [[-1 for i in range(v)] for j in range(v)]
    return adj_list

def prim(adj_list, v, s):
    # スタートを0とする
    min_d = 0
    heap = []
    used = []
    for i in range(v):
        used.append(False)
    used[s] = True
    for i in range(v):
        if adj_list[s][i] != -1:
            heapq.heappush(heap, (adj_list[s][i], i))
        #　スタートからつなぐことができる辺をheapに入れる

    while len(heap) != 0:
        cost, to = heapq.heappop(heap)
        if used[to]:
            continue
        min_d += cost
        used[to] = True
        for i in range(v):
            if adj_list[to][i] != -1:
                heapq.heappush(heap, (adj_list[to][i], i)) 
            #集合に入れた頂点からつなぐことができる辺をheapに入れる

    return min_d

def main():
    v = int(input())
    adj_list = make_adj_list(v)
    for i in range(v):
        adj_list[i] = [int(j) for j in input().split()]
    min_d = prim(adj_list, v, 0)
    print(min_d)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
 #Treeอสิระท่ีเช่ือมต่อทกุๆVertixในGraph โดยพยายามหาค่าให้มีค่าต่ำที่สุดในการสร้าง

n = int(input()) #รับจำนวน node ทั้งหมด
a = []

for i in range(n):
    inp = input() #รับข้อมูลทั้งหมด
    if "-1" in inp:
        inp = inp.replace("-1","10000") #แทนที่ -1 ด้วย 100000
    a.append(list(map(int, inp.split()))) #splitข้อมูลเป็น int เก็บค่าข้อมูลไว้ใน list

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

while len(v) < n: #วน loop ตามจำนวน n 
    min_w   = 10000 #min weight
    min_idx = 0 #min index
    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())
inf = float('inf')
graphs = []

for i in range(n):
    weights = list(map(int, input().split()))
    weights = [inf if weight == -1 else weight for weight in weights]
    graphs.append(weights)
# print(graphs)
# M =graphs
color = ['WHITE' for _ in range(n)]
d = [inf for _ in range(n)]
p = [i for i in range(n)]


def prim():
    d[0] = 0
    p[0] = -1
    while True:
        min_cost = inf
        for i in range(n):
            if color[i] != 'BLACK' and d[i] < min_cost:
                min_cost = d[i]
                u = i
        if min_cost == inf:
            break
        color[u] = 'BLACK'

        for v in range(n):
            if color[v] != 'BLACK' and graphs[u][v] != inf:
                if graphs[u][v] < d[v]:
                    d[v] = graphs[u][v]
                    p[v] = u
                    color[v] = 'GRAY'


prim()
# print(d)
# print(p)
print(sum(d))

Submission status: Accepted

Solution code:
import heapq

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

q = []

visited = [False]*n

adjs = []
sum_cost = 0
node = 0
visited[node] = True
cnt = 1

while 1:
    for i in range(n):
        if M[node][i] != -1 and visited[i] == False:
            heapq.heappush(q, (M[node][i], i))
    while 1:
        mincost,node = heapq.heappop(q)
        if visited[node] == False:
            break
    sum_cost += mincost
    visited[node] = True
    cnt += 1
    if cnt == n:
        break


print(sum_cost)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(sys.stdin.readline() for _ in range(n)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split()) for _ in range(N))) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections
N = int(sys.stdin.readline())
G = tuple(tuple(map(int,sys.stdin.readline().rstrip().split()) for _ in range(N))) # multi line with multi param

INF = float("inf")
W = [INF]*N
A = set(range(N))
T = set()

def add(e):
  T.add(e)
  for i,w in enumerate(G[e]):
    if not i in T and w != -1:
      W[i] = min(W[i],w)
  if not A-T:#W[-1] = -INF
    return -1
  m = min((W[i],i) for i in A-T)
  #print(W,T,m)
  return m[1]

n = add(0)
W[0] = 0
while len(T) < len(G):
  n = add(n)
print(sum(W))