POJ 1258

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int n,ans;
int mn[105];
bool vis[105];
int g[105][105];

int main(){
	freopen("1258.in","r",stdin);
	while(scanf("%d",&n)!=EOF){
		memset(mn,0,sizeof(mn));
		memset(vis,false,sizeof(vis));
		memset(g,0,sizeof(g));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&g[i][j]);
		memset(mn,0x7f,sizeof(mn));
	    memset(vis, false, sizeof(vis));
	    mn[1]=0;
	    for(int i=1;i<=n;i++){
	        int k=0;
	        for(int j=1;j<=n;j++)
	            if(!vis[j]&&(mn[j]<mn[k]))
	                k=j;
	        vis[k]=true;
	        for(int j=1;j<=n;j++)
	            if(!vis[j]&&(g[k][j]<mn[j]))
	                mn[j]=g[k][j];
	    }
	    int ans=0;
	    for(int i=1;i<=n;i++)
	        ans+=mn[i];
	    printf("%d\n",ans);
	}
	return 0;
}