Cod sursă (job #757136)

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), fin.tie(0);
using namespace std;
ifstream fin("zapada.in");
ofstream fout("zapada.out");

class edge
{
public:
    int x, y, cost;

    edge(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }

    bool operator<(const edge& a) const
    {
        return this->cost < a.cost;
    }
};

class Graph
{
private:
    int n;
    vector<vector<pair<int, int>>> adj;

public:
    Graph(int n) : n(n), adj(n + 1) {}

    void addEdge(int x, int y, int cost)
    {
        adj[x].emplace_back(y, cost);
        adj[y].emplace_back(x, cost);
    }

    int prim()
    {
        int costMin = 0;
        vector<bool> inTree(n + 1, false);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, 1}); // cost, node

        while (!pq.empty())
        {
            int u = pq.top().second;
            int c = pq.top().first;
            pq.pop();

            if (inTree[u])
                continue;

            inTree[u] = true;
            costMin += c;

            for (auto& neighbor : adj[u])
            {
                int v = neighbor.first;
                int costUV = neighbor.second;

                if (!inTree[v])
                {
                    pq.push({costUV, v});
                }
            }
        }

        return costMin;
    }
};

int main()
{
    fastio
    int n, m, k;
    fin >> n >> m >> k;

    Graph G(n);

    for (int i = 0; i < m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        G.addEdge(x, y, cost);
    }

    int c0 = G.prim();
    fout << c0 << '\n';

    for (int i = 0; i < k; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        G.addEdge(x, y, cost);
        int ck = G.prim();
        fout << ck << '\n';
    }
    return 0;
}