spider.cpp

#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <queue>
#include <utility>
#include <map>
 
using namespace std;
 
 
class mycmp{
public:
  bool operator()( const pair<int,int> & lhs, const pair<int,int> & rhs ) const{
    return (lhs.first-rhs.first)>0;
  }
};
 
int main(void){
  int nodeNO, linkNO;
  while (scanf("%d %d", &nodeNO, &linkNO)==2){
    int len =0;
    set<int> Set;
    set<int> Set2;
    multimap<int, pair<int,int> > mmp;
    priority_queue<pair<int,int>, vector<pair<int,int> >, mycmp> pq;  ////
    pair<int,pair<int,int> > max =  make_pair(0, make_pair(0,0));
 
    for (int i=0; i < linkNO; i++){
      int u,v,l;
      scanf("%d %d %d",&u, &v,&l);
      pair<int,pair<int,int> > tmp = make_pair(l, make_pair(u,v));
      Set2.insert(u);
      Set2.insert(v);
      if (l>max.first){
	if (max.first>0)
	  {
	    mmp.insert(make_pair(max.second.second,make_pair(max.first,max.second.first)));
	    mmp.insert(make_pair(max.second.first,make_pair(max.first,max.second.second)));
	  }
	max = tmp;
      }else {
	mmp.insert(make_pair(v,make_pair(l,u)));
	mmp.insert(make_pair(u,make_pair(l,v)));
      }
    }
    Set.insert(max.second.first);   
    Set.insert(max.second.second);
    len -= max.first;
    multimap<int,pair<int,int> >::iterator it;
    while ((it = mmp.find(max.second.first))!=mmp.end()){
      //      printf("it+=<%d,%d> \n", it->second.first, it->second.second);
      pq.push(it->second);
      mmp.erase(it);
    }
 
    while ((it = mmp.find(max.second.second))!=mmp.end()){
      //      printf("it*=<%d,%d> \n", it->second.first, it->second.second);
      pq.push(it->second);
      mmp.erase(it);
    }
 
    while (!pq.empty()){
      pair<int,int> tm = pq.top();
      pq.pop();
      //      printf("tm=<%d,%d> \n",tm.first, tm.second);
      if (Set.find(tm.second) == Set.end()){
	//	printf("len = %d ; new len = %d; tm = %d\n", len , len +tm.first, tm.first);
	len += tm.first;
	Set.insert(tm.second);
	while ((it = mmp.find(tm.second))!=mmp.end()){
	  // printf("it=<%d,%d> \n", it->second.first, it->second.second);
 
	  pq.push(it->second);
	  mmp.erase(it);
	}
      }
    }    
    if (!mmp.empty() || ((int)Set2.size())< nodeNO)
      printf("disconnected\n");
    else
      printf("%d\n",len);
  }
 
  return 0;
}