Cow Marathon
After hearing about the epidemic of obesity in the USA, Farmer John wants his cows to get more exercise, so he has committed to create a bovine marathon for his cows to run. The marathon route will include a pair of farms and a path comprised of a sequence of roads between them. Since FJ wants the cows to get as much exercise as possible he wants to find the two farms on his map that are the farthest apart from each other (distance being measured in terms of total length of road on the path between the two farms). Help him determine the distances between this farthest pair of farms.
有n个农田和m条路，以及每条路的方向（方向在这道题中没有用），求最长的一条路，也就是两点间的最大距离，即树的直径.
Input
- Lines 1…: Same input format as “Navigation Nightmare”.
Output
- Line 1: An integer giving the distance between the farthest pair of farms.
Sample Input
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
Sample Output
52
Hint
The longest marathon runs from farm 2 via roads 4, 1, 6 and 3 to farm 5 and is of length 20+3+13+9+7=52.
vj又崩了，交不了，先存上
这道题的输入就是输入农场数n和路的条数m，
然后接下来m行是连接的两个农场和之间的距离（路是无向的）
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
int n,m;//n是农场数，m是路的个数
int a,b,cost;//两个农场的位置以及距离（存的时候两个方向都要存）
char d;
int dis[50005];//到每个农场的距离
int vis[50005];
int ed,ans,num;
int head[50005];
struct cow{
int from;//农场的序号1
int to;//农场的序号2
int next;
int llng;//距离
//friend bool operator<(cow a,cow b){
// return a.llng <b.llng ;
//}
};
cow e1[100005];
void add(int a,int b,int c){
e1[num].from =a;
e1[num].to =b;
e1[num].llng =c;
e1[num].next =head[a];
head[a]=num++;
}
void bfs(int x){
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
queue<int> que;
que.push(x);
vis[x]=1;
ans=0;
while(!que.empty()){
int u,v,i;
u=que.front();
//cout<<"u:"<<u<<endl;
que.pop();
for(i=head[u];i!=-1;i=e1[i].next ){
v=e1[i].to ;
//cout<<"v:"<<v<<endl;
if(!vis[v]){
if(dis[v]<dis[u]+e1[i].llng )
dis[v]=dis[u]+e1[i].llng;
vis[v]=1;
que.push(v);
// cout<<"v:::::"<<v<<endl;
}
}
}
for(int i=1;i<=n;i++){
if(dis[i] >ans){
ans=dis[i];
ed=i;
// cout<<"ans:"<<ans<<" "<<i<<endl;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(),cout.tie();
cin>>n>>m;
int num=1;
memset(head,-1,sizeof(head));
for(int i=0;i<m;i++){
cin>>a>>b>>cost>>d;
add(a,b,cost);
add(b,a,cost);
}
bfs(1);
bfs(ed);
cout<<ans<<endl;
return 0;
}
/*
7 8
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
7 6 67 S
7 5 76 W
*/
（样例是过了，就是不知道会不会超时。。）
