莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

• 从 1 号点出发，就是个很裸的求最小生成树的板子题

可参考： Prim算法求最小生成树

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
int w[N][N];
int dist[N];
bool st[N];

int prim()
{
    //初始化 dist 数组，从 1 号点出发
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    //最小生成树的权值
    int res=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;

        res+=dist[t];
        st[t]=true;

        for(int j=1;j<=n;j++) dist[j]=min(dist[j],w[t][j]);
    }

    return res;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)    
        for(int j=1;j<=n;j++)
            cin>>w[i][j];

    cout<<prim()<<endl;

    return 0;
}