PKU 2631 Roads in the North

http://poj.org/problem?id=2631
重み付き無向木が与えられるので、最も遠い点同士の距離を求めろというような問題。

木の直径を求める。

vector<PI> G[10000];
bool vis[10000];
int ans;

int dij(int v){
  memset(vis,0,sizeof(vis));
  priority_queue<PI> q;
  q.push(mp(0,v));
  int ret=v;
  while(!q.empty()){
    int cc=-q.top().F;
    int cv=q.top().S;
    q.pop();
    if(vis[cv])continue;

    vis[cv]=true;
    ret=cv;
    ans=cc;
    FOR(it,G[cv]){
      if(vis[it->F])continue;
      q.push(mp(-cc-it->S,it->F));
    }
  }
  return ret;
}

main(){
  int a,b,c;
  while(cin>>a>>b>>c){
    --a,--b;
    G[a].pb(mp(b,c));
    G[b].pb(mp(a,c));
  }
  dij(dij(0));
  cout<<ans<<endl;
}