1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7  8 const int INF = 99999999 ; 9 const int maxn = 105 ;10 11 int map[maxn][maxn];12 int visit[maxn];13 int low[maxn];14 15 int main (){16     int n;17     while (~scanf ("%d",&n)){18         for (int i=1;i<=n;i++){19             for (int j=1;j<=n;j++){20                 scanf ("%d",&map[i][j]);21             }22             map[i][i]=INF;23         }24         int ans=0;25         memset (visit,0,sizeof visit);26         int pos=1;visit[1]=1;27         for (int i=1;i<=n;i++)28             low[i]=map[pos][i];29         int mi=INF;30         for (int i=1;i<n;i++){31             mi=INF;32             for (int j=1;j<=n;j++)33                 if (visit[j]==0&&low[j]<mi){34                     mi=low[j];pos=j;35                 }36             ans+=mi;visit[pos]=1;37             for (int j=1;j<=n;j++)38                 if (!visit[j])39                     low[j]=min(low[j],map[pos][j]);40         }41         printf ("%d\n",ans);42     }43     return 0;44 }