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
#include <cstdio>
#include <algorithm>

struct edge {
	int a, b;
};
edge t[2000 * 2000 + 10];
int dis[2014][2014];
int FU[2014];
int n;

bool cmp(edge a, edge b) {
	return dis[a.a][a.b] < dis[b.a][b.b];
}

int find(int x) {
	return x ^ FU[x] ? FU[x] = find(FU[x]) : x;
}

int main() {
	int nr = 0;
	scanf("%d", &n);
	for(int i = 0; i <= n; ++i)
		FU[i] = i;
	for(int i = 0; i < n; ++i)
		for(int j = i + 1; j <= n; ++j) {
			scanf("%d", dis[i] + j);
			t[nr].a = i;
			t[nr++].b = j;
		}
	std::sort(t, t + nr, cmp);
	long long sum = 0;
	for(int i = 0; i < nr; ++i) {
		if(find(t[i].a) != find(t[i].b)) {
			sum += dis[t[i].a][t[i].b];
			FU[find(t[i].a)] = find(t[i].b);
		}
	}
	printf("%lld\n", sum);
}