Cod sursă (job #639167)

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
FILE*in=fopen("zapada.in","r");
FILE*out=fopen("zapada.out","w");
const int NMAX=10007;
int n,m,k,i,x,y,c,ival,dad[NMAX],tnod,costdad[NMAX],mat[NMAX][NMAX];
long long cost;
bool b[NMAX],activotore;
struct drum
{
    int tat,nod,val;
};
drum el,mmin;
vector<drum> adj[NMAX];
priority_queue<drum> pq;
inline bool operator<(drum a,drum b)
{
    return a.val>b.val;
}
struct drumplus
{
    int nod,val,act;
};
drumplus ax;
vector<drumplus> vec[NMAX];
void dfs(int nd)
{
    for(auto t:vec[nd])
    {
        if(t.act==0&&dad[t.nod]==0)
        {
            if(t.nod==ival)
            {
                activotore=1;
            }
            costdad[t.nod]=t.val;
            dad[t.nod]=nd;
            dfs(t.nod);
        }
    }
}
int main()
{
    fscanf(in,"%d%d%d",&n,&m,&k);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        el.nod=y;
        el.val=c;
        el.tat=x;
        adj[x].push_back(el);
        el.nod=x;
        el.tat=y;
        adj[y].push_back(el);
    }
    b[1]=1;
    for(auto t:adj[1])
    {
        pq.push(t);
    }
    for(i=1;i<=n-1;i++)
    {
        el=pq.top();
        pq.pop();
        while(b[el.nod]==1)
        {
            el=pq.top();
            pq.pop();
        }
        ax.nod=el.nod;
        ax.val=el.val;
        ax.act=0;
        vec[el.tat].push_back(ax);
        ax.nod=el.tat;
        vec[el.nod].push_back(ax);
        b[el.nod]=1;
        cost=(long long)(cost+el.val);
        for(auto t:adj[el.nod])
        {
            if(b[t.nod]==0)
            {
                pq.push(t);
            }
        }
    }
    fprintf(out,"%lld\n",cost);
    for(i=1;i<=k;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        memset(dad,0,sizeof(dad));
        mmin.val=0;
        activotore=0;
        ival=y;
        dad[x]=-1;
        dfs(x);
        tnod=y;
        while(dad[tnod]!=-1)
        {
            if(mmin.val<costdad[tnod])
            {
                mmin.val=costdad[tnod];
                mmin.tat=dad[tnod];
                mmin.nod=tnod;
            }
            tnod=dad[tnod];
        }
        if(mmin.val>c)
        {
            for(int it=0;it<vec[mmin.tat].size();it++)
            {
                if(vec[mmin.tat][it].nod==mmin.nod)
                {
                    vec[mmin.tat][it].act=1;
                }
            }
            for(int it=0;it<vec[mmin.nod].size();it++)
            {
                if(vec[mmin.nod][it].nod==mmin.tat)
                {
                    vec[mmin.nod][it].act=1;
                }
            }
            ax.act=0;
            ax.nod=y;
            ax.val=c;
            vec[x].push_back(ax);
            ax.nod=x;
            vec[y].push_back(ax);
            cost=(long long)(cost+c);
            cost=(long long)(cost-mmin.val);
        }
        fprintf(out,"%lld\n",cost);
    }
}