记录编号	614390	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4384.[郑轻校赛 2026] 好想吃马斯卡彭喵！	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	26.780 s
提交时间	2026-04-08 15:55:44	内存使用	34.51 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2010;

int n;
ll w[MAXN][MAXN];
ll dis[MAXN];
bool vis[MAXN];

ll prim()
{
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	ll ans=0;
	for(int i=0;i<=n;i++)
	{
		int u=-1;
		for(int j=0;j<=n;j++) if(!vis[j]&&(u==-1||dis[j]<dis[u])) u=j;
		vis[u]=1;
		ans+=dis[u];
		for(int v=0;v<=n;v++) if(!vis[v]&&w[u][v]<dis[v]) dis[v]=w[u][v];
	}
	return ans;
}

int main()
{
	freopen("nosay.in","r",stdin);
	freopen("nosay.out","w",stdout);
	cin>>n;
	memset(w,0x3f,sizeof(w));
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			cin>>w[i-1][j];
			w[j][i-1]=w[i-1][j];
		}
	}
	cout<<prim()<<endl;
	return 0;
}