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 <iostream>
#include <cstdio>
#include <list>
using namespace std;
#define INF 2000000000
#define ll long long
int n,g[2001][2001],d[2001];

list<int> rw;
list<int>::iterator it,it2;

int main(int argc, char** argv) {
	ios_base::sync_with_stdio(0);
	cin >> n;
	for (int i=0;i<n;i++) {
		for (int j=i+1;j<=n;j++) {
			cin >> g[i][j];
			g[j][i]=g[i][j];
		}
	}
	d[0]=0;
	for (int i=1;i<=n;i++) {
		rw.push_front(i);
		d[i]=INF;
	}
	int w=0;
	ll ans=0;
	while (!rw.empty()){
		int dmin=INF;
		for (it=rw.begin();it!=rw.end();it++) {
			if ((g[w][*it])<d[*it]) d[*it]=g[w][*it];
			if (d[*it]<dmin) {dmin=d[*it]; it2=it;}
		}
		w=*it2;
		ans+=dmin;
		rw.erase(it2);
	}
	cout << ans;
	return 0;
}