Cod sursă (job #811901)

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

ifstream in("zapada.in");
ofstream out("zapada.out");
int n, m, k;
pair<int, pair<int, int>> v[100005];
vector<pair<int, int>> vec[10005];
int tata[10005];
int dim[10005];

int rad(int x)
{
    if(x == tata[x])
    {
        return x;
    }

    int r = rad(tata[x]);
    tata[x] = r;
    return r;
}

void unire(int x, int y)
{
    int rx = rad(x);
    int ry = rad(y);

    if(rx == ry)
    {
        return;
    }

    if(dim[ry] > dim[rx])
    {
        swap(rx, ry);
    }

    tata[ry] = rx;
    dim[rx] += dim[ry];
}

int check(int x, int y)
{
    return (rad(x) == rad(y));
}

void bfs(int start, int fin)
{
    queue<int> q;
    dim[start] = 0;
    q.push(start);

    while(!q.empty())
    {
        int nod = q.front();

        q.pop();

        if(nod == fin)
        {
            return;
        }

        for(auto it: vec[nod])
        {
            if(dim[it.first] == 0)
            {
                dim[it.first] = dim[start] + it.second;
                q.push(it.first);
            }
        }
    }
}

int main()
{
    in>>n>>m>>k;

    int x, y, z;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y>>z;

        v[i] = {z, {x, y}};
    }

    for(int i = 1; i<=n; i++)
    {
        tata[i] = i;
        dim[i] = 1;
    }

    sort(v + 1, v + m + 1);

    int cnt = n - 1;
    int ans = 0;
    for(int i = 1; i<=m; i++)
    {
        if(cnt == 0)
        {
            break;
        }

        pair<int, pair<int, int>> it = v[i];

        if(check(it.second.first, it.second.second) == 0)
        {
            unire(it.second.first, it.second.second);
            ans += it.first;
            cnt--;

            vec[it.second.first].push_back({it.second.second, it.first});
            vec[it.second.second].push_back({it.second.second, it.first});
        }
    }

    out<<ans<<'\n';

    for(int t = 1; t<=k; t++)
    {
        in>>x>>y>>z;

        for(int i = 1; i<=n; i++)
        {
            dim[i] = -1;
        }

        bfs(x, y);

        out<<ans<<'\n';
    }

    return 0;
}