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
#include<iostream>
#include<vector>
#include<set>

#define VECUINT std::vector<unsigned int>
#define VV std::vector<VECUINT >
#define ULL unsigned long long int
#define PII std::pair<unsigned int, unsigned int>

int main(){
	std::ios_base::sync_with_stdio(false);
	
	unsigned int n;
	std::cin>>n;
	VV Koszty(n, VECUINT(n));
	for(unsigned int i=0;i<n;++i)
		for(unsigned int j=i;j<n;++j)
			std::cin>>Koszty[i][j];
	
	std::vector<bool> Osiagalne(n,false);
	VECUINT MinimalneKrawedzie(Koszty[0]);
	std::set<PII> Krawedzie;
	for(unsigned int i=0;i<n;++i) Krawedzie.insert(PII(MinimalneKrawedzie[i],i));
	ULL R=0;
	while(!Krawedzie.empty()){
		PII c=*Krawedzie.begin();
		Krawedzie.erase(Krawedzie.begin());
		R+=c.first,Osiagalne[c.second]=true;
		for(unsigned int i=1;i<=c.second;++i)
			if(!Osiagalne[i-1]&&Koszty[i][c.second]<MinimalneKrawedzie[i-1]){
				Krawedzie.erase(PII(MinimalneKrawedzie[i-1],i-1));
				MinimalneKrawedzie[i-1]=Koszty[i][c.second];
				Krawedzie.insert(PII(MinimalneKrawedzie[i-1],i-1));				
			}
		for(unsigned int i=c.second+1;i<n;++i)
			if(!Osiagalne[i]&&Koszty[c.second+1][i]<MinimalneKrawedzie[i]){
				Krawedzie.erase(PII(MinimalneKrawedzie[i],i));
				MinimalneKrawedzie[i]=Koszty[c.second+1][i];
				Krawedzie.insert(PII(MinimalneKrawedzie[i],i));
			}
	}
	
	std::cout<<R<<"\n";
	
	return 0;
}