模板-U9559邻接矩阵DFS遍历+Prim

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<numeric>
using namespace std;
const int MAXV=1001,INF=1000001;
int N,M;
int d[MAXV];//候选边数组,d[i]为顶点i与当前树的最短距离(i与当前树的所有顶点距离的最小值)
bool vest[MAXV];//若vest[i]已并入树中,则vest[i]=true;
int G[MAXV][MAXV];//图的边权值
int sum=0,cnt=0;//最小生成树权值和
bool visit[MAXV]= {false};
void DFS(int i)
{
    visit[i]=true;
    for(int j=0; j<N; j++)
    {
        if(visit[j]==false&&G[i][j]!=INF)
            DFS(j);
    }
}
int Prim(int v)//v为起点
{
    int ans=0;//最小生成树边权之和

    //下面这一段,和Dijkstra算法一模一样
    fill(d,d+MAXV,INF);
    d[v]=0;
    for(int i=0; i<N; i++)
    {
        int u=-1,MIN=INF;
        for(int j=0; j<N; j++)
        {
            if(vest[j]==false&&d[j]<MIN)
            {
                u=j;
                MIN=d[j];
            }
        }

        if(u==-1)
            return -1;

        //从这里开始,就和Dijkstra算法不一样了
        vest[u]=true;
        ans+=d[u];

        for(int v=0; v<N; v++)
        {
            if(vest[v]==false&&G[u][v]!=INF&&G[u][v]<d[v])
                d[v]=G[u][v];
        }
    }
        return ans;
}
int main()
{
    while(cin>>N>>M)
    {
        if(N==0)
            return 0;
        fill(G[0],G[0]+MAXV*MAXV,INF);
        fill(vest,vest+MAXV,false);
        cnt=0;
        for(int i=0; i<M; i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            G[a-1][b-1]=c;
            G[b-1][a-1]=c;
        }
        for(int i=0; i<N; i++)
        {
            if(visit[i]==false)
            {
                cnt++;
                DFS(i);
            }
        }
        if(cnt>1)
            cout<<"?"<<endl;
        else
            cout<<Prim(0)<<endl;
    }
    return 0;
}