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
#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

priority_queue<pair<int, pair<int, int> > > Q;
vector<int> S[2005];
vector<int> E[2005];
int bekannt[2005][2005];

int main()
{
	ios_base::sync_with_stdio(0);
	long long int n, start, ende, kosten, wynik=0, EE, SS, ile=0, x;
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		for(int j=i; j<=n; j++)
		{
			cin >> kosten;
			Q.push(make_pair( (-1)*kosten, make_pair(i, j) ));
			}
		}
	while(!Q.empty())
	{
		//cout << ile << endl;
		
		x=(-1)*Q.top().first;
		start=Q.top().second.first;
		ende=Q.top().second.second;
		Q.pop();
		
		if(bekannt[start][ende]==1) continue;
		
		if(x!=0) ile++;
		bekannt[start][ende]=1;
		wynik=wynik+x;
		
		if(ile==n) break;
		
		for(int i=0; i<S[start].size(); i++)
		{
			EE=S[start][i];
			if(EE<ende) 
			{
				if(bekannt[EE+1][ende]==1) continue;
				Q.push(make_pair( 0 , make_pair(EE+1,ende) ));
				}
			else
			{
				if(bekannt[ende+1][EE]==1) continue;
				Q.push(make_pair( 0 , make_pair(ende+1,EE) ));
				}	
			}
		
		for(int i=0; i<S[ende+1].size(); i++)
		{
			EE=S[ende+1][i];
			if(bekannt[start][EE]==1) continue;
			Q.push(make_pair( 0 , make_pair(start,EE) ));
			}
			
		for(int i=0; i<E[start-1].size(); i++)
		{
			SS=E[start-1][i];
			if(bekannt[SS][ende]==1) continue;
			Q.push(make_pair( 0 , make_pair(SS,ende) ));
			
			}	
		
		for(int i=0; i<E[ende].size(); i++)
		{
			SS=E[ende][i];
			if(SS<start)
			{
				if(bekannt[SS][start-1]==1) continue;
				Q.push(make_pair( 0 , make_pair(SS,start-1) ));
				}
			else
			{
				if(bekannt[start][SS-1]==1) continue;
				Q.push(make_pair( 0 , make_pair(start,SS-1) ));
				}	
			}
		
		
		S[start].push_back(ende);
		E[ende].push_back(start);
		}
	
	cout << wynik << endl;
	
	return 0;
}