[//]: # 大家注意这里，很坑的一个地方

题目描述

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
int n;
const int N = 105;
int g[N][N];
int dis[N];
bool st[N];

int prim()
{
    memset(dis,0x3f,sizeof dis);

    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 || dis[j] < dis[t]))
            {
                 t= j;
            }
        }

       for(int j = 1; j <= n; j++)
        {
            if(j != t)      //要判断一下，要不然g[t][t] = 0的。
                dis[j] = min(dis[j],g[t][j]);
        }


        if(i) res += dis[t];  




        st[t] = true;
    }

    return res;
}
int main()
{
    cin >> n;


        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                cin >> g[i][j];
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                g[i][j] = min(g[i][j],g[j][i]);
            }
        }
        cout <<  prim() << endl;

}