题意分析

1.题目描述： Farmer John 希望他的奶牛能够得到更多的锻炼，因此他计划为奶牛们创建一个牛马拉松比赛。马拉松的路线将包括一对农场和连接它们的一系列道路。由于 FJ 希望奶牛们能够得到尽可能多的锻炼，他需要找到地图上距离最远的两个农场（距离定义为两个农场之间路径上所有道路的总长度）。请帮助他计算最远农场对之间的距离。

2.输入格式：

第一行包含两个整数 n 和 q，分别表示农场的数量和道路的数量。 接下来的 q 行，每行描述一条道路，格式为 x y w c，其中 x 和 y 是道路连接的两个农场编号，w 是道路的长度，c 是一个字符（可以忽略，可能是用于其他用途）。 3.输出格式：

输出一个整数，表示最远的一对农场之间的距离。

解题思路

问题建模： 这是一个典型的树的最长路径问题，即树的直径问题。树的直径是指树中任意两个节点之间最长路径的长度。 树的直径可以通过深度优先搜索（DFS）来解决： 从任意一个节点出发，进行一次 DFS，找到距离它最远的节点 u。 从节点 u 出发，再进行一次 DFS，找到距离它最远的节点 v。u 和 v 之间的路径就是树的直径。

代码实现

#include<iostream>
#include<queue>
#include<string.h>
#include<cstdio>
using namespace std;
const int maxn=1e6+5;
struct EDGE{int to,cap,next;}edge[maxn<<1];
struct node{
	int u,tot;
	node(int x,int y):u(x),tot(y){}
};
int n,x,y,w,q,cnt,res,maxcap,maxvex,head[maxn];char ch;bool vis[maxn];
queue<node> que;
void add_edge(int u,int v,int w){
	edge[cnt].to=v;
	edge[cnt].cap=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
void bfs(int u,int cap,int &maxcap,int &maxvex){
	while(!que.empty())que.pop();
	memset(vis,false,sizeof(vis));
	que.push(node(u,cap));vis[u]=true;
	while(!que.empty()){
		node nod=que.front();que.pop();
		for(int i=head[nod.u];~i;i=edge[i].next){
			int v=edge[i].to;
			if(!vis[v]){
				vis[v]=true;
				que.push(node(v,nod.tot+edge[i].cap));//先把其邻接点都入队，并标记为已访问
			}
		}
		if(nod.tot>maxcap)maxcap=nod.tot,maxvex=nod.u;//再更新当前节点的深度
	}
}
int main(){
	while(~scanf("%d%d",&n,&q)){
		memset(head,-1,sizeof(head));cnt=0;
		while(q--){
			scanf("%d %d %d %c",&x,&y,&w,&ch);
			add_edge(x,y,w);
			add_edge(y,x,w);
		}
		maxcap=0,maxvex=1;
		bfs(1,0,maxcap,maxvex);maxcap=0;
		bfs(maxvex,0,maxcap,maxvex);
		printf("%d\n",maxcap);
	}
	return 0;
}