蚂蚁上树

蚂蚁上树（Sauteed Vermicelli with minced
Pork），又名肉末粉条，是四川省及重庆市的特色传统名菜之一。因肉末贴在粉丝上，形似蚂蚁爬在树枝上而得名。这道菜具体的历史，已不可考。但在四川省、重庆市一带，该菜很常见。

蚂蚁上树通常由粉丝（或者粉条）、肉末为主料，辅以胡萝卜、姜、葱、豆瓣酱等辅料制作而成。成菜后，口味清淡，爽滑美味，色泽红亮，食之别有风味

蚂蚁想知道这棵树上距离最远的两个点之间的距离

给你一个具有 n 个节点的树

求这棵树上距离最远的两个点之间的距离

输入格式
第一行一个整数 n ，(1≤n≤104)

接下来 n−1 行，每行三个整数 x,y,z 表示 x 与 y 之间有一条长度为 z 的边 (1≤x,y≤n,1≤z≤104)

输出格式
一个整数表示树上距离最远的两个点之间的距离

样例
input
5
1 2 9
1 3 3
1 5 2
2 4 10
output
22

解题思路：
其实就是树的直径模板题，不过我用链式前向星做，把edge[]数组开小了，导致一直wa，原来数组开小了不一定会提示re；借此提醒自己。

Code：

#include<bits/stdc++.h>
using namespace std;
int dis[10005],vis[10005],head[10005],temp=0;

struct node{
	int w,to,next;
};
node edge[20005];//开成其他数组两倍大小，u->v,v->w两次加边 
int cnt=0;
void add(int u,int v,int w){
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

void bfs(int x){
	memset(vis,0,sizeof(vis));
	memset(dis,0,sizeof(dis));
	vis[x]=1;dis[x]=0;temp=0;
	queue<int>q;
	q.push(x);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			if(!vis[v]){
				if(dis[v]<dis[u]+edge[i].w){
					dis[v]=dis[u]+edge[i].w;
					if(dis[v]>dis[temp]){
						temp=v;
					}
				}
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
int main(){
	int n;
	cin>>n;
	memset(head,-1,sizeof(head));
	for(int i=0;i<n-1;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	bfs(1);
	bfs(temp);
	//bfs(temp);
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dis[i]);
	}
	cout<<ans<<endl;
	
	return 0;
}