Špijuni

#include <bits/stdc++.h>
using namespace std;

struct talk {
    int who, withWhom, price;
    bool operator<(const talk& rhs) const
    {
        return price < rhs.price;
    }
};

struct noden {
    int parent;
    int rank;
};

// Varijablen
int n;
vector<talk> talks;
noden nodens[1010];
talk result[1010];
int spyPrice[1010];

void load() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int val;
            cin >> val;
            if (i == j) continue;
            talk t;
            t.who = min(i, j);
            t.withWhom = max(i, j);
            t.price = val;

            if (j < i) {
                talks.push_back(t);
            }

        }
    }
    for (int i = 0; i < n; i++) {
        cin >> spyPrice[i];
        talk mission;
        mission.who = n;
        mission.withWhom = i;
        mission.price = spyPrice[i];
        talks.push_back(mission);
    }
}

int finden(int i)
{
    if (nodens[i].parent != i)
        nodens[i].parent = finden(nodens[i].parent);

    return nodens[i].parent;
}

void unionen(int x, int y)
{
    int xroot = finden(x);
    int yroot = finden(y);

    if (nodens[xroot].rank < nodens[yroot].rank)
        nodens[xroot].parent = yroot;
    else if (nodens[xroot].rank > nodens[yroot].rank)
        nodens[yroot].parent = xroot;
    else {
        nodens[yroot].parent = xroot;
        nodens[xroot].rank++;
    }
}

void solve() {
    sort(talks.begin(), talks.end());
    for (int i = 0; i <= n; i++) {
        nodens[i].parent = i;
        nodens[i].rank = 0;
    }

    int e = 0;
    int i = 0;
    while (e < n) {
        talk t = talks[i++];

        int x = finden(t.who);
        int y = finden(t.withWhom);

        if (x != y) {
            result[e++] = t;
            unionen(x, y);
        }
    }
    int rez = 0;
    for (int i = 0; i < e; i++) {
        rez += result[i].price;
    }
    cout << rez;
}

int main() {
    load();
    solve();
}