プリム法

最小全域木問題に対してのプリム法による解法
AOJ ALDS1_12_A Minimum Spanning Tree

・まずスタートの点を決める
・「既に到達した点」から「まだ到達していない点」へ行く辺の中で一番コストの低い辺を探す
・その辺を採用し、辺の先の点は「既に到達した点」に加える
・すべての点に到達したところで最小全域木が完成する

問題文が
i    点jへのコスト 点j+1へのコスト 点j+2へのコスト
i+1  点jへのコスト 点j+1へのコスト 点j+2へのコスト
という感じのときに使いやすい

計算量はO(N^2)
でちょっと使いにくいかも

#入力
n = int(input())
A = []
for _ in range(n):
  a = list(map(int,input().split()))
  A.append(a)
ans = 0

#到達したかどうかのboolリスト
used = [False]*n
#適当に0番目から開始
used[0] = True
#到達した点の数のカウントを行う
cnt = 1

while cnt<n:
  mincost = float("INF")
  point_temp = -1
  #現時点で到達がTrueになっている点の行き先のうちで
  for i in range(n):
    if used[i]:
      for j in range(n):
        #行き先への到達がTrueになっておらず、-1でもない点のコストを全検索
        if used[j]:
          continue
        if A[i][j] == -1:
          continue
        if A[i][j] < mincost:
          mincost = A[i][j]
          point_temp = j
  if point_temp == -1:
    print("error")
    exit()
  #最小コストだった点をTrueに変更する
  used[point_temp] = True
  ans += mincost
  cnt += 1
  
print(ans)       


クラスカル法、プリム法は
下記のサイトを参考にしました。
ありがとうございます。
algo-logic.info