package main

import (
    "fmt"
    "math"
)

func main() {
    graph := [][]int{
        {0, 11, 55},
        {math.MaxInt32, 0, 22},
        {math.MaxInt32, math.MaxInt32, 0}}
    ret := prim(graph)
    fmt.Println(ret)
}

// 请保证graph是连通图
// graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路
// 返回值是最小连通图的路径之和
func prim(graph [][]int) int {
    size := len(graph)
    distances := make([]int, size)
    visit := make([]bool, size)
    visit[0] = true
    for i := 0; i < size; i++ {
        distances[i] = graph[0][i]
    }
    sum := 0
    for i := 1; i < size; i++ {
        minPath := math.MaxInt32
        minIndex := -1
        for j := 0; j < size; j++ {
            if !visit[j] && distances[j] < minPath {
                minPath = distances[j]
                minIndex = j
            }
        }
        if minIndex == -1 {
            return sum
        }
        visit[minIndex] = true
        sum += minPath
        for j := 0; j < size; j++ {
            if !visit[j] && distances[j] > graph[minIndex][j] {
                distances[j] = graph[minIndex][j]
            }
        }
    }
    return sum
}