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
#include<iostream>
#include<vector>
using namespace std;
int cena[2000][2000];
char znana[2000];
struct zakres{int p;int k;int l;int r;long long int subc;int subd;};
int mini[4];
vector <zakres> V;
int main() {
ios_base::sync_with_stdio(0);
int n;
int lokminp;
int lokmink;
int lokminp2;
int lokmink2;
long long int wynik=0;
cin >> n;
int nieznane=n;
for(int a=0;a<n;a++){for(int b=0;b<a;b++){cena[a][b]=-2;}}
for(int b=0;b<n;b++){znana[b]=0;}
for(int a=0;a<n;a++){for(int b=a;b<n;b++){cin>>cena[a][b];}}
V.resize(n);
for(int i=0;i<n;i++){V[i].p=i;V[i].k=i;V[i].l=i;V[i].r=i;V[i].subc=2000000000;}

for(int a=0;a<V.size();a++){
	for(int b=0;b<a;b++){if(cena[b][a]+cena[b][a-1]<V[a].subc){V[a].subc=cena[b][a]+cena[b][a-1];V[a].subd=a-b;}}
	for(int b=V.size()-1;b>a;b--){if(cena[a][b]+cena[a+1][b]<V[a].subc){V[a].subc=cena[a][b]+cena[a+1][b];V[a].subd=a-b;}}
}

while(nieznane!=0){
mini[0]=0;
mini[1]=0;
mini[2]=2000000000;
for(int a=0;a<V.size();a++){/*cout<<"\n\n"<<a<<"\n\n";*/
	if(znana[a]==0){
		if(cena[V[a].p][V[a].k]<mini[2]){/*cout<<V[a].p<<" "<<V[a].k<<" "<<mini[2];*/mini[2]=cena[V[a].p][V[a].k];mini[0]=V[a].p;mini[1]=V[a].k;mini[3]=a;}
		if(V[a].subc<mini[2]){mini[3]=a;mini[2]=V[a].subc;mini[0]=-2;}
	}
}

if(mini[0]==-2){if(V[mini[3]].subd>0){cena[mini[3]-V[mini[3]].subd][mini[3]]=0;cena[mini[3]-V[mini[3]].subd][mini[3]-1]=0;}
				else{cena[mini[3]][mini[3]-V[mini[3]].subd]=0;cena[mini[3]+1][mini[3]-V[mini[3]].subd]=0;}}
/*
cout<<"\n0 "<<mini[0]<<"\n1 "<<mini[1]<<"\n2 "<<mini[2]<<"\n3 "<<mini[3]<<"\n";*/

znana[mini[3]]=1;
wynik=wynik+mini[2];
nieznane=nieznane-1;
lokminp=V[mini[3]].l;
lokmink=V[mini[3]].r;
if(lokminp>0){lokminp=lokminp-1;}
if(lokmink<n-1){lokmink=lokmink+1;}
for(int i=lokminp;i<mini[3];i++){
	V[i].r=V[mini[3]].r;
	}

for(int i=mini[3]+1;i<=lokmink;i++){
	V[i].l=V[mini[3]].l;
	}
	
for(int i=lokminp;i<=lokmink;i++){/*cout<<"I"<<i;*/
	if(znana[i]==0){/*cout<<"Y";*/
		lokminp2=V[i].p;
		lokmink2=V[i].k;
		for(int a=V[i].l;a<=lokminp2;a++){for(int z=i;z<=V[i].r;z++){if(cena[a][z]<cena[V[i].p][V[i].k]){V[i].p=a;V[i].k=z;}}}
		for(int a=lokmink2;a<=V[i].r;a++){for(int z=V[i].l;z<=i;z++){if(cena[z][a]<cena[V[i].p][V[i].k]){V[i].p=z;V[i].k=a;}}}
		}
	}
/*
for(int i=0;i<n;i++){
cout<<"\n"<<i<<" "<<V[i].p<<" "<<V[i].k<<" "<<V[i].l<<" "<<V[i].r<<" "<<(int)znana[i];}
cout<<"\n\n";*/
}
cout<<wynik;
}