Cod sursă (job #641360)

#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<int> parent;
std::vector<unordered_map<int,int> > v;
std::vector<muchie_cost> vkuri;
int findparent(int x){
  if(parent[x]==x)
    return x;
  return parent[x]=findparent(parent[x]);
}

struct de_qt{
  int first,second,n1,n2;
};
int cost=0;

void bfs(int source,int target,int costuri){
  std::vector<int> vis(n+1,0);
  queue<de_qt> qt;
  int n1=0,n2=0;
  qt.push({source,0,source,source});
  vis[source]=1;
  int maxim=0;
  bool gasit=0;
  while(!gasit){

    for(auto it=v[qt.front().first].begin();it!=v[qt.front().first].end();it++){
      if(!vis[it->first]){
        vis[it->first]=1;
        if(it->first==target){
          gasit=true;
          if(it->second>qt.front().second){
            maxim=it->second;
            n1=qt.front().first;
            n2=it->first;
          }else{
            maxim=qt.front().second;
            n1=qt.front().n1;
            n2=qt.front().n2;
          }
        break;
        }
        if(qt.front().second>=it->second)
        {
            int s=it->first;
          qt.push({s,qt.front().second,qt.front().n1,qt.front().n2});
        }else {
            int s=it->first,tr=it->second;
          qt.push({s,tr,qt.front().first,s});
        }

      }
    }

    qt.pop();
  }

  if(maxim<=costuri){
    fout<<cost<<'\n';
  }else{
    v[n1][n2]=0;
    v[n2][n1]=0;
    v[source][target]=costuri;
    v[target][source]=costuri;
    cost=cost-maxim+costuri;
    fout<<cost<<'\n';
  }


}


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

  fin>>n>>m>>k;
  parent.resize(n+1,0);
    v.resize(n+1);
  vkuri.resize(k+1);
  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;

  while(!pq.empty() && nr<n){

    if(findparent(pq.top().x)!=findparent(pq.top().y)){
      parent[parent[pq.top().x]]=parent[pq.top().y];
      nr++;
      v[pq.top().x][pq.top().y]=pq.top().c;
        v[pq.top().y][pq.top().x]=pq.top().c;
      cost+=pq.top().c;
    }

    pq.pop();
  }
  fout<<cost;
  fout<<'\n';
  for(int i=1;i<=k;i++){
    fin>>a>>b>>c;
    bfs(a,b,c);
  }

  return 0;
}