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
52
53
54
55
56
57
58
59
60
61
// Krzysztof Piesiewicz
// Kuglarz [A] PA 2014
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 2007, DB = 0;

class Seg {
public:
	int i, j, c;
};

class Ve {
public:
	int f;
	vector< Ve* > v;
};

inline bool operator<( Seg a, Seg b ) {
	return a.c < b.c;
}

void update( Ve *v, int f ) {
	v->f = f;
	for( vector< Ve* >::iterator it = v->v.begin(); it != v->v.end(); it++ )
		if( (*it)->f != f )
			update( *it, f );
}

int n, size, cnt;
long long res;
Seg s[ MAX_N * MAX_N ];
Ve g[ MAX_N ];

int main() {
	scanf( "%d", &n );
	for( int i = 1; i <= n; i++ )
		for( int j = i; j <= n; j++ ) {
			s[ size ].i = i;
			s[ size ].j = j;
			scanf( "%d", &s[ size++ ].c );
		}
	for( int i = 0; i <= n; i++ )
		g[ i ].f = i;
	sort( s, s + size );
	for( int i = 0; i < size && cnt < n; i++ ) {
		if( DB )
			printf( "i %d, c %d, %d - %d\n", i, s[ i ].c, s[ i ].i, s[ i ].j );
		if( g[ s[ i ].i - 1 ].f != g[ s[ i ].j ].f ) {
			cnt++;
			res += s[ i ].c;
			g[ s[ i ].i - 1 ].v.push_back( &g[ s[ i ].j ] );
			g[ s[ i ].j ].v.push_back( &g[ s[ i ].i - 1 ] );
			update( &g[ s[ i ].j ], g[ s[ i ].i - 1 ].f );
		}
	}
	printf( "%Ld\n", res );
	return 0;
}