51Nod1212 无向图最小生成树

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int map[1001][1001];
int d[1001];
int visit[1001];
const int INF=1<<30;
int main()
{
    int i,j,m,n;
    scanf("%d%d",&n,&m);
    memset(visit,1,sizeof(visit));
    memset(d,0,sizeof(d));
    for(i=0;i<=n;i++)
            for(j=0;j<=n;j++)
                map[i][j]=map[j][i]=(i==j?0:INF);
    for(i=0;i<m;i++)
    {
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
//      if(map[a][b]>c)//保证权值最小，不然会WA的 
        map[a][b]=map[b][a]=c;
    } 
    //prim              
    for(i=1;i<=n;i++)
      d[i]=map[i][1];
    int sum=0;
    visit[1]=0;
    for(i=1;i<=n;i++)
    {
      int minn=INF;
      int temp;
      for(j=1;j<=n;j++)
        if(visit[j]&&d[j]<minn)
        {
          minn=d[j];
          temp=j;
        }
      if(minn==INF)
        break;
      sum+=minn;
      visit[temp]=0;
      for(j=1;j<=n;j++)
        if(visit[j]&&d[j]>map[j][temp])
          d[j]=map[j][temp];      
    }
    cout<<sum<<endl;
  
  return 0;
}