【POJ】1985 - Cow Marathon（树的直径）

7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S

52

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 40000
int n,m;
vector<int> mapp[MAX+5];
vector<int> dis[MAX+5];
int f[MAX+5];		//距离当前点的距离 
bool vis[MAX+5];
void init()
{
	for (int i = 1 ; i <= n ; i++)
	{
		mapp[i].clear();
		dis[i].clear();
	}
}
int dfs(int x)
{
	int ans;		//最远点 
	int maxx = 0;		//最大距离 
	queue<int> q;		//存放根 
	CLR(vis,false);
	CLR(f,0);
	f[x] = 0;
	q.push(x);
	vis[x] = true;
	while (!q.empty())
	{
		int st = q.front();
		q.pop();
		for (int i = 0 ; i < mapp[st].size() ; i++)
		{
			if (!vis[mapp[st][i]])		//该点没有用过 
			{
				q.push(mapp[st][i]);
				f[mapp[st][i]] = f[st] + dis[st][i];
				vis[mapp[st][i]] = true;
				if (f[mapp[st][i]] > maxx)
				{
					maxx = f[mapp[st][i]];
					ans = mapp[st][i];		//记录节点 
				}
			}
		}
	}
	return ans;
}
int main()
{
	while (~scanf ("%d %d",&n,&m))
	{
		init();
		for (int i = 1 ; i <= m ; i++)
		{
			int t1,t2,t3;
			char t4[3];
			scanf ("%d %d %d %s",&t1,&t2,&t3,t4);
			mapp[t1].push_back(t2);
			dis[t1].push_back(t3);
			mapp[t2].push_back(t1);		//求树的直径一定要双向存图 
			dis[t2].push_back(t3);
		}
		int st = dfs(1);		//任意从一点开始bfs
		int ans = dfs(st);
		printf ("%d\n",f[ans]);
	}
	return 0;
}