Cod sursă (job #718805)

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 10005;
const int MAXM = 100005;
const int MAXK = 1005;
const int INF = 1e9;

struct Edge {
    int u, v, w;
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};

int N, M, K;
vector<Edge> edges, new_edges;
vector<int> parent, rank_;
vector<bool> used;

int find(int x) {
    if (parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    x = find(x), y = find(y);
    if (rank_[x] > rank_[y]) swap(x, y);
    parent[x] = y;
    rank_[y] += rank_[x];
}

void kruskal() {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        rank_[i] = 1;
    }
    for (const auto& edge : edges) {
        int u = edge.u, v = edge.v, w = edge.w;
        if (find(u) != find(v)) {
            merge(u, v);
            new_edges.push_back(edge);
            used.push_back(true);
        }
        else {
            new_edges.push_back(edge);
            used.push_back(false);
        }
    }
}

int main() {
    ifstream fin("zapada.in");
    ofstream fout("zapada.out");
    fin >> N >> M >> K;
    parent.resize(N + 1);
    rank_.resize(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }
    kruskal();
    vector<int> ans(K + 1);
    for (int i = 0; i <= K; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        int res = 0;
        for (int j = 0; j < new_edges.size(); j++) {
            if (used[j]) res += new_edges[j].w;
            else if (new_edges[j].u == x && new_edges[j].v == y) res += c;
        }
        ans[i] = res;
    }
    for (int i = 0; i <= K; i++) {
        fout << ans[i] << '\n';
    }
    return 0;
}