poj - 1258

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f; 
int mapp[1005][1005];
int n;
int sum;
int lowcast[1005];
int nearvex[1005];
void prim()
{
    sum=0;
    for(int i=1;i<=n;i++)
    {
        lowcast[i]=mapp[1][i];
        nearvex[i]=1;
    }
    nearvex[1]=-1;
    for(int i=1;i<n;i++)
    {   int min=INF;
        int v=-1;
        for(int j=1;j<=n;j++)
        {
            if(nearvex[j]!=-1&&min>lowcast[j])
            {
                min=lowcast[j];
                v=j;
            }
        }
            nearvex[v]=-1;
            sum=sum+lowcast[v];
        //  printf("sum=%d\n",sum);
            for(int j=1;j<=n;j++)
            {
                if(nearvex[j]!=-1&&mapp[v][j]<lowcast[j])
                {
                   lowcast[j]=mapp[v][j];
                   nearvex[j]=v;             //还行没用。。。。
                }   
            }
        
    }
        printf("%d\n",sum); 
}
int main()
{
  while(scanf("%d",&n)!=EOF)
  {
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            
            {
                scanf("%d",&mapp[i][j]);
            } 
        }
    }
    prim();
    }
}