Cod sursă (job #759496)

#include <fstream>
#include <vector>
#include <queue>
#define pii pair<int,int>
#define dim 10002
#define inf 0x3f3f3f3f
using namespace std;

ifstream cin("zapada.in");
ofstream cout("zapada.out");

int n,m,k,cost_total;

vector<pii>V[dim];
priority_queue<pii,vector<pii>,greater<pii>>Q;

int v[dim],d[dim];

void prim(){
    Q.push({0,1});
    for(int i=2;i<=n;++i) d[i]=inf;
    
    while(!Q.empty()){
        int cst=Q.top().first;
        int nod=Q.top().second;
        
        if(v[nod]){
            Q.pop();
            continue;
        }
        
        v[nod]=1;
        cost_total+=cst;
        
        for(auto nbr:V[nod]){
            int vec=nbr.first;
            int cst=nbr.second;
            
            if(d[vec]>cst && !v[vec]){
                d[vec]=cst;
                Q.push({cst,vec});
            }
        }
    }
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        V[a].push_back({b,c});
        V[b].push_back({a,c});
    }
    prim();
    cout<<cost_total<<'\n';
    for(int i=1;i<=k;++i){
        int a,b,c;
        cin>>a>>b>>c;
        V[a].push_back({b,c});
        V[b].push_back({a,c});
        
        cost_total=0;
        for(int i=1;i<=n;++i) v[i]=0;
        
        prim();
        cout<<cost_total<<'\n';
    }
    return 0;
}