poj 2631 Roads in the North (树的直径)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月12日 星期二 13时03分39秒
  4File Name :code/poj/2631.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E4+7;
 34int n,m;
 35vector < pi> edge[N];
 36int lst;
 37int ans;
 38int d[N];
 39bool vis[N];
 40
 41
 42void bfs( int s)
 43{
 44    ms(d,0x3f);
 45    ms(vis,false);
 46    queue<int>q;
 47    q.push(s);
 48    vis[s] = true;
 49    d[s] =  0 ;
 50
 51    while (!q.empty())
 52    {
 53	int u = q.front() ; q.pop();
 54	lst = u ;
 55//	cout<<"u:"<<u<<endl;
 56	int siz = edge[u].size();
 57
 58	for ( int i = 0 ; i < siz ; i++)
 59	{
 60	    int v = edge[u][i].fst;
 61	    if (vis[v]) continue;
 62	    vis[v] = true;
 63	    d[v] = d[u] + edge[u][i].sec;
 64	    ans = max(d[v],ans);
 65	    q.push(v);
 66	}
 67    }
 68
 69    int mx = 0;
 70    for ( int i = 1 ; i <= n ; i++)
 71    {
 72//	cout<<"i:"<<i<<" d[i]:"<<d[i]<<endl;
 73	if (d[i]>mx)
 74	{
 75	    mx = d[i];
 76	    lst = i ;
 77	}
 78    }
 79
 80}
 81int main()
 82{
 83	#ifndef  ONLINE_JUDGE 
 84	freopen("code/in.txt","r",stdin);
 85  #endif
 86
 87	int u,v,w;
 88	m = 0;
 89	n = 0;
 90	while (scanf("%d%d%d",&u,&v,&w)!=EOF)
 91	{
 92	    edge[u].push_back(make_pair(v,w));
 93	    edge[v].push_back(make_pair(u,w));
 94	    m++;
 95	    n = max(n,u);
 96	    n = max(n,v);
 97	}
 98	ans = inf;
 99	bfs(1);
100	ans = 0;
101//	cout<<"lst:"<<lst<<endl;
102	bfs(lst);
103	cout<<ans<<endl;
104
105  #ifndef ONLINE_JUDGE  
106  fclose(stdin);
107  #endif
108    return 0;
109}