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; }