Cod sursă (job #676059)

#include <bits/stdc++.h>
#define N 10001

using namespace std;


ifstream fin("zapada.in");
ofstream fout("zapada.out");

int n,m,k;
long long sol=0;
vector< pair<int,pair<int,int>> >muchii;
vector<pair<int,int>> a[N];


int father[N];
int grad[N];


int Find(int x)
{
    if( !father[x] )
        return x;
    else
    {
        int f=Find( father[x] );
        father[x]=f;
        return f;
    }
}

void Union(int x,int y)
{
    int tx=Find(x),ty=Find(y);
    if( tx!=ty )
    {
        if( grad[tx]==grad[ty] )
        {
            grad[tx]++;
            father[ty]=tx;
        }
        if( grad[tx]>grad[ty] )
        {
            father[ty]=tx;
        }
        if( grad[tx]<grad[ty] )
        {
            father[tx]=ty;
        }
    }
}


void Evaluare_muchie()
{
    int x,y,c;
    fin >> x >> y >> c;
    /// distanta de la x la ....
    vector<int> dist(N,0);
    queue<int> q;
    q.push(x);
    dist[x]=1;

    while( !q.empty() )
    {
        int cur=q.front();
        q.pop();
        for(auto i: a[cur])
            if( !dist[ i.second ] )
            {
                dist[i.second]=dist[cur]+1;
                q.push( i.second );
            }
    }
    /// reconstituire drum
    int pas=dist[y],nod=y;
    int candidatx=-1,candidaty=-1,candidatpret=-1;
//cout << y << " ";
    while( nod!=x )
    {
        int aux,pret;
        pas--;
        for(auto i:a[nod] )
            if( dist[ i.second ]==pas )
            {
                aux=i.second,pret=i.first;
            }
        /// prel muchie nod-aux
        if( pret>c )
        {
            if( candidatx==-1 or candidatpret<pret )
            {
                candidatx=nod;
                candidaty=aux;
                candidatpret=pret;
                ///
            }
        }
//cout << nod << " ";
        nod=aux;
    }
//cout << "\n";

    if( candidatx!=-1 )
    {
        sol-=candidatpret;
        sol+=c;
        ///
/// a[candidatx][candidaty]=a[candidaty][candidatx]=0;
        for(unsigned int i=0;i<a[candidatx].size();i++)
            if( a[candidatx][i].second==candidaty )
            {
                a[candidatx].erase(a[candidatx].begin()+i);
                break;
            }
        for(unsigned int i=0;i<a[candidaty].size();i++)
            if( a[candidaty][i].second==candidatx )
            {
                a[candidaty].erase(a[candidaty].begin()+i);
                break;
            }
        ///
        a[x].push_back( {c,y} );
        a[y].push_back( {c,x} );
    }
    fout << sol << '\n';
}

void Kruskal()
{
    sort(muchii.begin(),muchii.end());
    for(int i=0;i<m;i++)
    {
        int x= muchii[i].second.first;
        int y= muchii[i].second.second;
        int c= muchii[i].first;
        if( Find(x)!=Find(y) )
        {
            sol+=c;
            Union(x,y);

            a[x].push_back( {c,y} );
            a[y].push_back( {c,x} );
        }
    }
    fout << sol << '\n';
}

void Citire()
{
    fin >> n >> m >> k;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        muchii.push_back( { c,{x,y} } );
    }
    Kruskal();
    m=n-1;
    for(int i=1;i<=k;i++)
        Evaluare_muchie();
    fin.close();
    fout.close();
}
int main()
{
//ios_base::sync_with_stdio(false);
//    fin.tie(0);
    Citire();
    return 0;
}