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 <iostream>
#include <list>

using namespace std;

unsigned int rozwiaz();
unsigned int znajdz_najtanszy(bool * znane);

int n;
unsigned int ** c;

int main()
{
    // inicjuj i wczytaj dane

    cin >> n;

    c = new unsigned int *[n+1];
    for (int i=1 ; i<=n ; i++) {
        c[i] = new unsigned int[n+1];
    }

    for (int i=1 ; i<=n ; i++) {
        for (int j=i ; j<=n ; j++) {
            cin >> c[i][j];
        }
    }

    // tu sie zaczyna

    unsigned int wynik = rozwiaz();
    cout << wynik << endl;

    return 0;
}

unsigned int rozwiaz(){
    unsigned int suma = 0;
    bool * znane = new bool[n+1];
    for (int i=1 ; i<=n ; i++)
        znane[i] = false;
    for (int a=1 ; a<=n ; a++) {
        suma += znajdz_najtanszy(znane);
    }

    return suma;
}

unsigned int znajdz_najtanszy(bool * znane) {
    unsigned int min_c;
    int min_k = 0, i = 1;

    while (znane[i] == true) {
        i++;
    }
    min_k = i, min_c = c[i][i];
    while (i <= n) {
        if (znane[i] == false && c[i][i] < min_c) {
            min_k = i, min_c = c[i][i];
        }
        i++;
    }

    for (int i=1 ; i<=n ; i++) {
        if (znane[i] == true) {
            int j;
            for (j=i+1 ; j<n && znane[j] == true; j++);
            if (j<=n && znane[j] == false && c[i][j] < min_c)
                min_k = j, min_c = c[i][j];
            int k;
            for (k=j+1 ; k<=n && znane[k] == true; k++) {
                if (c[i][k] < min_c)
                    min_k = k, min_c = c[i][k];
            }
        }
    }

    for (int i=n ; i>=1 ; i--) {
        if (znane[i] == true) {
            int j;
            for (j=i-1 ; j>1 && znane[j] == true ; j--);
            if (j>=1 && znane[j] == false && c[j][i] < min_c) {
                min_k = j, min_c = c[j][i];
            }
            int k;
            for (k=j-1 ; k>=1 && znane[k] == true ; k--) {
                if (c[k][i] < min_c)
                    min_k = k, min_c = c[k][i];
            }
        }
    }

    znane[min_k] = true;
    return min_c;
}