Cod sursă (job #644201)

#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;
  }
};
struct cond2{
  size_t operator()(const muchie_cost &a,const muchie_cost &b) const{
    return a.c<=b.c;
  }
};

int n,m,k;

std::vector<unordered_map<int,int>> v;

std::vector<int> parent;

void dfs(int start,int finish,int cost,bool &gasit,std::vector<int> &vis,priority_queue<muchie_cost,std::vector<muchie_cost>, cond2>& pq){
  muchie_cost nod;
  if(start!=finish)
  {
    unordered_map<int,int>::iterator it;
    for(it=v[start].begin();it!=v[start].end() && !gasit;it++){
    if(!vis[it->first]){
      vis[it->first]=1;
      nod={start,it->first,it->second};
      dfs(it->first,finish,cost,gasit,vis,pq);
      vis[it->first]=0;
    }
  }
}else {
    gasit=true;
    return;
  }
  pq.push({nod.x,nod.y,nod.c});
}


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;
  for(int i=1;i<=m;i++){
    fin>>a>>b>>c;
    pq.push({a,b,c});
  }
  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;
      v[pq.top().x][pq.top().y]=pq.top().c;
      v[pq.top().y][pq.top().x]=pq.top().c;
    }
    pq.pop();
  }
  fout<<cost;
   fout<<'\n';
  for(int i=1;i<=k;i++){
    fin>>a>>b>>c;
  bool gasit=false;
  std::vector<int> vis(n+1,0);
  priority_queue<muchie_cost,std::vector<muchie_cost>, cond2> pq;
  dfs(a,b,c,gasit,vis,pq);

  if(pq.top().c>c){
    cost=cost-pq.top().c+c;
    v[pq.top().x][pq.top().y]=0;
    v[pq.top().y][pq.top().x]=0;
    v[a][b]=c;
    v[b][a]=c;
  }
  fout<<cost;
  fout<<'\n';
  }
  return 0;
}