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
#include<cstdio>
int k[2001][2001];
const int max=1000000001;
int n;

int minx(int y, int xl, int xp, int&x){
int m=max;
for(register int ix=xp;ix>=xl;ix--)if(k[y][ix]<m) m=k[y][ix],x=ix;
return m;  
}

int min(int p, int&x, int&y)
{
 int m=max,tx,tm; x=-1;
 for (int i=0;i<=p;i++)
 {tm=minx(i,p,n-1,tx);if (tm<m)m=tm,x=tx,y=i;}
 return m;  
}

main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
  for (int j=i,x;j<n;j++)
    scanf("%d",&x), k[i][j]=x,k[j][i]=x;
 
long long w=0;int x,y;
for (int i=0;i<n;i++) {
 w+=min(i,x,y);
 if (x>i){k[y][x]=max;k[x][y]=max;k[y][x]=k[x][y]=minx(i,0,i,x);} 
 }
printf("%lld\n",w);   
}
// napisane na szybko, moze beda 2 punkty :-)