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
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;

long long t[2000][2000];
pair<int,int> t2[4000000];
vector<long long>P[2001];
vector<long long>K[2001];
bool blok[2001][2001];
std::deque<int> kol;
int main(){
	int n,k=0;
	cin>>n;
	for(int i =0;i<n;i++)
		for(int j=i;j<n;j++){
			cin>>t[i][j];
			t2[k].first = t[i][j];
			t2[k].second = i*n+j;
			k++;
		}
	sort(t2,t2+k);
	int ile = 1;
	long long wynik = t2[0].first;
	P[t2[0].second/n].push_back(t2[0].second%n);
	K[t2[0].second%n].push_back(t2[0].second/n);
	blok[t2[0].second/n][t2[0].second%n]=true;
//	cout<<t2[0].first<<" P: "<<t2[0].second/n<<" "<<t2[0].second%n<<"\n";
	for(int i =1;i<k;i++){
		
		if(ile==n)break;
		
		int a = t2[i].second/n;
		int b = t2[i].second%n;
		if(blok[a][b])continue;
		wynik+= t2[i].first;
		kol.push_back(t2[i].second);
		P[a].push_back(b);
			K[b].push_back(a);
			
		while(!kol.empty()){
		//	cout<<t2[i].first<<" P: "<<t2[i].second/n<<" "<<t2[i].second%n<<"\n";
			int c = kol.front();
			kol.pop_front();
			a = c/n;
			b = c%n;
		
			blok[a][b]=true;
			
			for(int j=0;j<P[a].size();j++){
				if(P[a][j]<b){
					if(!blok[P[a][j]+1][b]){
						blok[P[a][j]+1][b] = true;
						kol.push_back((P[a][j]+1)*n+b);
						P[P[a][j]+1].push_back(b);
						K[b].push_back(P[a][j]+1);
					}else
						break;
				}
				if(P[a][j]>b){
					if(!blok[b+1][P[a][j]]){
						blok[b+1][P[a][j]] = true;
						kol.push_back((b+1)*n+P[a][j]);
						P[b+1].push_back(P[a][j]);
						K[P[a][j]].push_back(b+1);
					}else
						break;
				}
			}
			
				
			for( int j = 0; j<P[b+1].size();j++){
				if(!blok[a][P[b+1][j]]){
					blok[a][P[b+1][j]]=true;
					P[a].push_back(P[b+1][j]);
					K[P[b+1][j]].push_back(a);
					kol.push_back((a)*n+P[b+1][j]);
				}else
					break;
			}
				for(int j=0;j<K[b].size();j++){
				if(K[b][j]>a){
					if(!blok[a][K[b][j]-1]){
						blok[a][K[b][j]-1] = true;
						kol.push_back(a*n+(K[b][j]-1));
						P[a].push_back(K[b][j]-1);
						K[K[b][j]-1].push_back(a);
					}else
						break;
				}
				if(K[b][j]<a){
					if(!blok[K[b][j]][a-1]){
						blok[K[b][j]][a-1] = true;
						kol.push_back(K[b][j]*n+(a-1));
						P[K[b][j]].push_back(a-1);
						K[a-1].push_back(K[b][j]);
					}else
						break;
				}
			}
		if(a>0)		
			for(int j=0;j<K[a-1].size();j++)
				if(!blok[K[a-1][j]][b]){
					blok[K[a-1][j]][b] = true;
					kol.push_back(K[a-1][j]*n+(b));
					P[K[a-1][j]].push_back(b);
					K[b].push_back(K[a-1][j]);
				}else
					break;
		}
		ile++;
	}
//	for(int i =0;i<n;i++)
//		cout<<P[i].size()<<" "<<K[i].size()<<"\n";
//	cout<<ile<<"\n";
	cout<<wynik<<"\n";
	return 0;	
}