Cod sursă (job #641354)

#include <bits/stdc++.h>
using namespace std;

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

struct muchie_cost{
  int x,y,c;

};

struct cond{
 size_t operator()(const muchie_cost &a,const muchie_cost &b) const {
    return a.c>=b.c;
  }
};


int n,m,k;
std::vector<std::vector<pair<int,int> > > v;
std::vector<std::vector<pair<int,int> > > temp;
std::vector<int> parent;

int findparent(int x){
  if(parent[x]==x)
    return x;
  return parent[x]=findparent(parent[x]);
}

int main(int argc, char const *argv[]) {

  fin>>n>>m>>k;
  v.resize(n+1);
  parent.resize(n+1,0);
  for(int i=1;i<=n;i++){
    parent[i]=i;
  }
  int a,b,c;
  priority_queue<muchie_cost,std::vector<muchie_cost>, cond> pq;
  priority_queue<muchie_cost,std::vector<muchie_cost>, cond> pqaux;
  for(int i=1;i<=m;i++){
    fin>>a>>b>>c;
    v[a].push_back({b,c});
    v[b].push_back({a,c});
    pq.push({a,b,c});
  }
  pqaux=pq;
  int nr=1;
  int cost=0;
  while(!pq.empty() && nr<n){

    if(findparent(pq.top().x)!=findparent(pq.top().y)){
      parent[parent[pq.top().x]]=parent[pq.top().y];
      nr++;
      cost+=pq.top().c;
    }
    pq.pop();
  }
  fout<<cost;
   fout<<'\n';
    pq=pqaux;
  for(int i=1;i<=k;i++){
    fin>>a>>b>>c;
    v[a].push_back({b,c});
    v[b].push_back({a,c});
    pqaux.push({a,b,c});
    pq=pqaux;
    parent.resize(n+1,0);
    for(int j=1;j<=n;j++){
    parent[j]=j;
  }
    int nr=1;
  int cost=0;
  while(!pq.empty() && nr<n){

    if(findparent(pq.top().x)!=findparent(pq.top().y)){
      parent[parent[pq.top().x]]=parent[pq.top().y];
      nr++;
      cost+=pq.top().c;
    }
    pq.pop();
  }
  fout<<cost;
  fout<<'\n';
  }
  return 0;
}