题目:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQDOxEzX3xCZlhXam9VbsUmepNXZy9CXwJWZ3xCdh1mcvZ2Lc1zaHRGcWdUYuVzVa9GczoVdG1mWfVGc5RHLwIzX39GZhh2csATMflHLwEzX4xSZz91ZsAzMfRHLGZkRGZkRfJ3bs92YskmNhVTYykVNQJVMRhXVEF1X0hXZ0xiNx8VZ6l2cssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLxkTOxEGN1Q2MwQzYhhjNzYzX0AzN1QTM3AzLcFTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
#include <bits/stdc++.h>
using namespace std;
int pos[105][105],dis[105],vis[105];
int n;
int inf=0x3f3f3f3f;
int prim()
{
memset(dis,inf,sizeof(dis));
int res=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&(t==-1||dis[j]<dis[t])) t=j;
}
if(i&&dis[t]==inf) return inf;
if(i) res+=dis[t];
vis[t]=1;
for(int j=1;j<=n;j++) dis[j]=min(dis[j],pos[t][j]);
}
return res;
}
int main()
{
cin>>n;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
pos[i][j]=i==j?0:inf;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>pos[i][j];
}
}
int t=prim();
cout<<t<<endl;
return 0;
}