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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <utility>
using namespace std;
void read(map<pair<int,int>,int > &m ,int N){
	for(int i=0;i<N;++i){
		for(int j=i+1;j<=N;++j){
			int v; cin>>v;
			m[make_pair(i,j)]=v;
	}
	}
}
void t(map<pair<int,int>,int > &m,set<pair<int,int> > &s,pair<int,int> rem){
		set<pair<int,int>> temp;
		for(auto ist=s.begin();ist!=s.end();++ist)
		{
			if(ist->first==rem.second)
				{auto ii=m.find(make_pair(rem.first,(ist->second))); if(ii!=m.end()) { temp.insert(ii->first);  m.erase(ii);} }
			if(ist->second==rem.first)
						{auto ii=m.find(make_pair(ist->first,rem.second)); if(ii!=m.end()) {temp.insert(ii->first); m.erase(ii);}}
			if(ist->first==rem.first)
						{auto ii=m.find(make_pair(min(ist->second,rem.second),max(ist->second,rem.second))); if(ii!=m.end()) {temp.insert(ii->first); m.erase(ii);}}
			if(ist->second==rem.second)
								{auto ii=m.find(make_pair(min(ist->first,rem.first),max(ist->first,rem.first))); if(ii!=m.end()) {temp.insert(ii->first); m.erase(ii);}}

		}
for(auto itx:temp) t(m,s,itx);

}

long long findK(map<pair<int,int>,int > &m,int N){
	set<pair<int,int> > s;
	long long K=0;
	//find the smallest el
	while(! m.empty()){
	auto it=(min_element(m.begin(),m.end(),[](pair<pair<int,int>,int > a, pair<pair<int,int>,int > b){return a.second<b.second;}));
	pair<int,int> rem=it->first;
	s.insert(it->first);
	K+=it->second;
	m.erase(it);
	t(m,s,rem);
	}
return K;
}

int main()
{
	int N;
	cin>>N;
	map<pair<int,int>,int > m;
	read(m,N);
	cout<<findK(m,N)<<endl;
	return 0;
}