10308:Roads in the North

問題文
http://uva.onlinejudge.org/external/103/10308.html

重み付きの無向の木が与えられるので
最遠頂点間の距離(木の直径と言う)を求める問題。

木の直径は２回の深さ優先探索で求めることができる。
まず適当な頂点から深さ優先探索して最も遠い頂点vを求める。
次にその最も遠い頂点から深さ優先探索でvから最も遠い頂点uを求める。
このu-v間の距離が木の直径となる。

時間制限が2secなので全頂点から深さ優先探索で試しても通るっぽい。

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<climits>
#include <string>
#include <sstream>

#define MAX_V 10001
 
using namespace std;
struct edge{int to, cost; };
typedef pair<int, int> P;

vector<edge>G[MAX_V];
bool vis[MAX_V];

P dfs(int v){
  vis[v]=true;
  P res(0,v);

  for(int i=0;i<G[v].size();i++){
    edge e=G[v][i];
    if(!vis[e.to]){
      P tmp=dfs(e.to);
      tmp.first+=e.cost;
      if(res.first<tmp.first)res=tmp;
    }
  }
  return  res;
}

int diameter(void){
  fill(vis,vis+MAX_V,false);
  P a = dfs(1);
  fill(vis,vis+MAX_V,false);
  P ans = dfs(a.second);
  return ans.first; 
}

void add_edge(int from,int to,int cost){
  edge e;
  e.to=to,e.cost=cost;
  G[from].push_back(e);
  e.to=from;
  G[to].push_back(e);
}
 
int main(void){
 
  int from,to,cost;
  string in;
 
  while(!cin.eof()){
    for(int i=0;i<MAX_V;i++)G[i].clear();
    while(getline(cin,in) && in!=""){
      stringstream ss(in);
      ss >> from >> to >> cost;
      add_edge(from,to,cost);
    }
    cout << diameter() << endl;
  }
  return 0;
}