刷题记录表

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
inline int read(int &a){a=0;int f=1;char c=getchar();if(c==EOF) return a=EOF;
for(;c<'0' || c>'9';c=getchar()){if(c=='-') f=-1;if(c==EOF) return a=EOF;}
for(;c<='9' && c>='0';a=a*10+c-'0',c=getchar());return a*=f;}
int n;
int c[2010][2010];
int f[2010],bj[2010];
ll ans;

int main()
{
	read(n);
	for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j++)
	read(c[i-1][j]),c[j][i-1]=c[i-1][j];
	f[0]=0;
	for(int i=1;i<=n;i++) f[i]=c[0][i];
	for(int i=1;i<=n;i++)
	{
		int sum=INF,k;
		for(int j=1;j<=n;j++)
		if(!bj[j] && f[j]<sum)
		sum=f[j],k=j;
		bj[k]=1,ans+=sum;
		for(int j=1;j<=n;j++)
		if(!bj[j] && f[j]>c[k][j])
		f[j]=c[k][j];
	}
	printf("%lld\n",ans);
	return 0;
}