Cod sursă (job #720026)

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

struct Street {
    int castle1;
    int castle2;
    int cost;

    Street(int c1, int c2, int c) : castle1(c1), castle2(c2), cost(c) {}
};

int main() {
	(void)!freopen("zapada.in", "r", stdin);
    (void)!freopen("zapada.out", "w", stdout);
    int N, M, K;
    cin >> N >> M >> K;

    vector<Street> streets;
    for (int i = 0; i < M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        streets.push_back(Street(x, y, c));
    }

    vector<Street> newStreets;
    for (int i = 0; i < K; i++) {
        int xi, yi, ci;
        cin >> xi >> yi >> ci;
        newStreets.push_back(Street(xi, yi, ci));
    }

    int C0 = INT_MAX;
    for (int i = 0; i < (1 << M); i++) {
        int cost = 0;
        vector<bool> cleared(M, false);


        for (int j = 0; j < M; j++) {
            if ((i >> j) & 1) {
                cost += streets[j].cost;
                cleared[j] = true;
            }
        }


        vector<bool> visited(N + 1, false);
        visited[1] = true; 
        int numVisited = 1;

        
        while (numVisited < N) {
            bool found = false;

            for (int j = 0; j < M; j++) {
                if (!cleared[j])
                    continue;

                if (visited[streets[j].castle1] && !visited[streets[j].castle2]) {
                    visited[streets[j].castle2] = true;
                    numVisited++;
                    found = true;
                }
                else if (!visited[streets[j].castle1] && visited[streets[j].castle2]) {
                    visited[streets[j].castle1] = true;
                    numVisited++;
                    found = true;
                }
            }

            if (!found)
                break;
        }

        
        if (numVisited == N)
            C0 = min(C0, cost);
    }

    cout << C0 << endl;

    for (int i = 0; i < K; i++) {
        C0 = INT_MAX;


        streets.push_back(newStreets[i]);


        for (int j = 0; j < (1 << streets.size()); j++) {
            int cost = 0;
            vector<bool> cleared(streets.size(), false);

            for (int k = 0; k < streets.size(); k++) {
                if ((j >> k) & 1) {
                    cost += streets[k].cost;
                    cleared[k] = true;
                }
            }

            vector<bool> visited(N + 1, false);
            visited[1] = true;
            int numVisited = 1;
               while (numVisited < N) {
                bool found = false;

                for (int k = 0; k < streets.size(); k++) {
                    if (!cleared[k])
                        continue;

                    if (visited[streets[k].castle1] && !visited[streets[k].castle2]) {
                        visited[streets[k].castle2] = true;
                        numVisited++;
                        found = true;
                    }
                    else if (!visited[streets[k].castle1] && visited[streets[k].castle2]) {
                        visited[streets[k].castle1] = true;
                        numVisited++;
                        found = true;
                    }
                }

                if (!found)
                    break;
            }

            if (numVisited == N)
                C0 = min(C0, cost);
        }

        cout << C0 << endl;
    }

    return 0;
}