プログラミングコンテストチャレンジブック演習「プリム法」

今回のお題はこちら

お題に書いてある通りコスト最小の辺とその辺で到達できる頂点を一つずつ加えていき、最小全域木を求める方法です。

INF = 2 ** 30
V = 10 #input
$cost = Array.new( V ).map!{ Array.new( V, 0 ) } #input

$used = Array.new(V, false)
$mincost = Array.new(V, INF)

$mincost[0] = 0
$totalCost = 0

def IsAllNodeUsed
  $used.each do |used_flg|
    return false unless used_flg
  end
  return true
end

while true
  break if IsAllNodeUsed
  
  addV = -1
  for i in 0..(V - 1)
    addV = i if !$used[i] && (addV == -1 || $mincost[i] < $mincost[addV])
  end
  
  $used[addV] = true
  $totalCost += $mincost[addV]
  
  for i in 0..(V - 1)
    $mincost[i] = [$mincost[i], $cost[addV][i]].min
  end
end