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

using namespace std;

typedef struct {
    int a;
    int b;
    int cost;
} item;

const int N_MAX = 2000;

vector<item> dane;

bool comp(const item &i, const item &j) {
    return i.cost < j.cost;
}

bool output[N_MAX][N_MAX];
int countt = 0;
int n;

void update(int a, int b) {
    if (output[a][b]) return;
    output[a][b] = true;
    countt += 1;

    for (int i = 0; i < n; ++i) {
        if (i < a) {
            if (output[i][a-1]) update(i, b);
        } else if (i < b) {
            if (output[a][i]) update(i+1, b);
        } else if (i > b) {
            if (output[a][i]) update(b+1, i);
        }
    }

    for (int i = 0; i < n; ++i) {
        if (i < a) {
            if (output[i][b]) update(i, a-1);
        } else if (i > a && i <= b) {
            if (output[i][b]) update(a, i-1);
        } else if (i > b) {
            if (output[b+1][i]) update(a, i);
        }
    }
}

int main() {
	scanf("%d\n", &n);
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			int c;
			scanf("%d", &c);
            item it;
            it.a = i; it.b = j; it.cost = c;
            dane.push_back(it);
            output[i][j] = false;
		}
	}
    sort(dane.begin(), dane.end(), comp);
    int count_max = n*(n+1)/2;
    long long int result = 0;
    int i = 0;
    while (countt < count_max) {
        if (!output[dane[i].a][dane[i].b]) {
            result += (long long int) dane[i].cost;
            update(dane[i].a, dane[i].b);
        }
        i++;
    }
    printf("%lld\n", result);
	return 0;
}