Cod sursă (job #521965)

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("zapada.in");
ofstream g("zapada.out");
int n,m,k,cost,tdx,tdy,tdc;
struct mc{int x,c;mc*n;}*a[10001];
struct doi{int c,f;}c[10001];
void add(int i)
{
    mc*h=new mc;
    h=a[i];
    while(h!=NULL)
    {
        if(c[h->x].c==0){c[h->x].c=h->c;c[h->x].f=i;}
        else if(c[h->x].c>0)if(c[h->x].c>h->c){c[h->x].c=h->c;c[h->x].f=i;}
        h=h->n;
    }
    h=a[i];
    while(h!=NULL)
    {
        a[i]=a[i]->n;
        delete(h);
        h=a[i];
    }
}
bool dfsf(int i,int p)
{
    if(i==m)return 1;
    mc*h=new mc;
    h=a[i];
    while(h!=NULL)
    {
        if(h->x!=p)if(dfsf(h->x,i))
        {
            if(h->c>tdc)
            {
                tdc=h->c;
                tdx=h->x;
                tdy=i;
            }
            return 1;
        }
        h=h->n;
    }
    return 0;
}
void delet()
{
    //tre sa invat stl
    mc*h=a[tdx];
    if(h->x!=tdy)
        while(h->n!=NULL)
        {
            if(h->n->x==tdy)
            {
                mc*del=h->n;
                h->n=h->n->n;
                delete(del);
                break;
            }
            h=h->n;
        }
    else {a[tdx]=a[tdx]->n;delete(h);}
    h=a[tdy];
    if(h->x!=tdx)
        while(h->n!=NULL)
        {
            if(h->n->x==tdx)
            {
                mc*del=h->n;
                h->n=h->n->n;
                delete(del);
                break;
            }
            h=h->n;
        }
    else {a[tdy]=a[tdy]->n;delete(h);}
}
int main()
{
    f>>n>>m>>k;
    for(int i=1;i<=n;++i)a[i]=NULL;
    for(int i=1;i<=m;++i)
    {
        int x,y,c;
        f>>x>>y>>c;
        mc*d=new mc;
        d->x=x;d->c=c;
        d->n=a[y];a[y]=d;
        d=new mc;
        d->x=y;d->c=c;
        d->n=a[x];a[x]=d;
    }
    c[1].c=-1;add(1);
    for(int i=1;i<n;++i)
    {
        int cm=100001,mi=0,mf=0;
        for(int i=1;i<=n;++i)
            if(c[i].c>0&&c[i].c<cm){mf=c[i].f;cm=c[i].c;mi=i;}
        add(mi);
        mc*d=new mc;
        cost+=cm;
        d->x=mi;d->c=cm;
        d->n=a[mf];a[mf]=d;
        d=new mc;
        d->x=mf;d->c=cm;
        d->n=a[mi];a[mi]=d;
        c[mi].c=-1;
    }
    g<<cost<<'\n';
    for(;0<k;--k)
    {
        int x,y,c;
        f>>x>>y>>c;
        m=y;
        dfsf(x,-1);
        if(tdc>c)
        {
            cost-=tdc-c;
            delet();
            mc*d=new mc;
            d->x=x;d->c=c;
            d->n=a[y];a[y]=d;
            d=new mc;
            d->x=y;d->c=c;
            d->n=a[x];a[x]=d;
        }
        g<<cost<<'\n';
    }
}