POJ 2631最長路探索,BFS

Roads in the North
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 1352
 
Accepted: 666
Description
Building and maintaining roads among communities in the far North is an expensive business. With this in mind, the roads are build such that there is only one route from a village to a village that does not pass through some other village twice.
Given is an area in the far North comprising a number of villages and roads among them such that any village can be reached by road from any other village. Your job is to find the road distance between the two most remote villages in the area.
The area has up to 10,000 villages connected by road segments. The villages are numbered from 1.
Input
Input to the problem is a sequence of lines, each containing three positive integers: the number of a village, the number of a different village, and the length of the road segment connecting the villages in kilometers. All road segments are two-way.
Output
You are to output a single integer: the road distance between the two most remote villages in the area.
Sample Input

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

Sample Output

22

Source
The UofA Local 1999.10.16
最長路の捜索は以前マトリックスの模型の題目をしたことがあります
これはチェーンテーブル形式ですが、アルゴリズムは同じで、まず任意の点を探して起点を作ることができて、それからBFSはこの点から最も遠い点を出して、それからこの点を起点にして以上の操作を繰り返して、今回見つけた点の起点からの距離は最も長い道です!!
書き方は双方向BFSもDFSも可能です.私はBFSが好きです.
先に交际を始める时わけがわからないCE、OJは私にMAXを変数にすることができないことを提示して、私はとても気がふさいで、私はmaxを変数にするのはすでに1回2回ではありませんて、どうしてこの时に私に注意しますか?でも結局はmaxxに変更するしかありません.の無駄に2つのCEに貢献しました...
Source Code
Problem: 2631
 
User: bingshen
Memory: 656K
 
Time: 47MS
Language: C++
 
Result: Accepted

Source Code

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>

using namespace std;

struct node
{
	int dis;
	int v;
};
bool flag[10005];
vector<node>map[10005];
int maxx;

int bfs(int s)
{
	int i,id;
	node k1,k2;
	queue<node>q;
	k1.v=s;
	k1.dis=0;
	q.push(k1);
	flag[s]=true;
	while(!q.empty())
	{
		k2=q.front();
		q.pop();
		for(i=0;i<map[k2.v].size();i++)
		{
			k1=map[k2.v][i];
			if(!flag[k1.v])
			{
				flag[k1.v]=true;
				k1.dis=k2.dis+map[k2.v][i].dis;
				if(k1.dis>maxx)
				{
					maxx=k1.dis;
					id=k1.v;
				}
				q.push(k1);
			}
		}
	}
	return id;
}

int main()
{
	int a,b,l,k;
	node p;
	while(scanf("%d%d%d",&a,&b,&l)!=EOF)
	{
		p.v=b;
		p.dis=l;
		map[a].push_back(p);
		p.v=a;
		map[b].push_back(p);
	}
	memset(flag,0,sizeof(flag));
	maxx=0;
	k=bfs(1);
	memset(flag,0,sizeof(flag));
	maxx=0;
	k=bfs(k);
	printf("%d/n",maxx);
	return 0;
}