10308

This is the problem to find the tree diameter.

#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <string.h>
#include <stdio.h>

#define ull unsigned long long
#define SZ 10002
#define FOR(i,a) for(int i=0;i<a;i++)

using namespace std;

vector<int> graph[SZ];
bool visit[SZ];
int distnce[SZ][SZ];
ull distnode[SZ];
ull max_dist=0;
int farthestnode;

void bfs(int u)
{
	int tmp;
	memset(visit,0,sizeof(visit));
	int next_node;
	max_dist=0;
	queue<int> q;
	q.push(u);
	distnode[u]=0;
	while(!q.empty())
	{
		tmp = q.front();
		q.pop();
		visit[tmp]=1;

		if(distnode[tmp]>max_dist)
		{
			max_dist=distnode[tmp];
			farthestnode = tmp;
		}
		for(int i=0;i<graph[tmp].size();i++)
		{
			next_node = graph[tmp][i];
			if(!visit[next_node])
			{
				distnode[next_node]=distnode[tmp]+distnce[tmp][next_node];
				q.push(next_node);
			}
		}

	}

}


int main()
{
	string s,s1;
	int from,dest,cost;
	stringstream ss;

	while(!cin.eof())
	{
		getline(cin,s);

		if(s=="")
		{
			cout<<0<<"\n";
			continue;
		}

		FOR(i,SZ)
		graph[i].clear();

		memset(distnce,0,sizeof(distnce));
		memset(distnode,0,sizeof(distnode));

		while(!cin.eof() && s.size()>0)
		{
			if(s=="")
			break;
			ss.clear();
			ss<<s;
			ss>>from>>dest>>cost;

			graph[from].push_back(dest);
			graph[dest].push_back(from);

			distnce[from][dest]=cost;
			distnce[dest][from]=cost;

			getline(cin,s);
		}

		bfs(1);
		bfs(farthestnode);

		cout<<max_dist<<"\n";

	}

	return 0;

}