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
#include<cstdio>
#include<algorithm>

enum {
	MAX = 2010
};

int graf[MAX][MAX];

int costs[MAX];
bool gotit[MAX];

int main()
{
	int n; scanf("%d", &n);
	for(int i = 0; i < n; i++)
		for(int j = i; j < n; j++)
		{
			int x; scanf("%d", &x);
			graf[i][j+1] = x;
			graf[j+1][i] = x;
		}
	for(int i = 0; i < n; i++)
		costs[i] = graf[n][i];
	long long sol = 0;
	for(int ii = 0; ii < n; ii++)
	{
		int min = -1;
		for(int i = 0; i < n; i++)
			if(!gotit[i] && (min == -1 || costs[i] < costs[min])) min = i;
		sol += costs[min];
		gotit[min] = 1;
		for(int i = 0; i < n; i++)
			if(graf[min][i] < costs[i]) costs[i] = graf[min][i];
	}
	printf("%lld\n", sol);
}