1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <algorithm>
#include <vector>

#define fru(j,n) for(int j=0;j<n;++j)
#define tr(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

const int MAXE= 2010005;
typedef pair<int,pii> pip;

pip E[MAXE];
int REP[2005];

int find(int x)
{
	if(x!=REP[x]) REP[x]=find(REP[x]);
	return REP[x];
}

int main()
{
	int n,c=0;
	scanf("%d",&n);
	fru(i,n+1) REP[i]=i;
	fru(i,n) fru(j,n-i)
	{
		int a;
		scanf("%d",&a);
		E[c++]=pip(a,pii(i,i+j+1));
	}
	sort(E,E+c);
	LL ans=0;
	fru(i,c)
	{
		int a=E[i].y.x,b=E[i].y.y;
		if(find(a)!=find(b))
		{
			ans+=E[i].x;
			REP[find(a)]=find(b);
		}
	}
	printf("%lld\n",ans);
	return 0;
}