2 条题解

  • 0
    @ 2022-12-10 17:50:50
    #include<bits/stdc++.h>
    using namespace std;
    struct twig{
    	int to;
    	int len;
    };
    int n,x,y,z;
    vector<twig> a[1005];
    int depth[1005];
    void dfs(int now,int fa)
    {
    	if(!a[now].empty())
    		for(auto it=a[now].begin();it!=a[now].end();it++)
    		{
    			int w=(*it).to,length=(*it).len;
    			if(w!=fa)
    			{
    				depth[w]=depth[now]+length;
    				dfs(w,now);
    			}
    		}
    }
    int main()
    {
    	cin>>n;
    	for(int i=1;i<n;i++)
    	{
    		cin>>x>>y>>z;
    		a[x].push_back((twig){y,z});
    		a[y].push_back((twig){x,z});
    	}
    	int maxdisroot=1,maxdis=0;
    	//寻找到点 1  距离最远的点 maxdisroot 
    	dfs(1,-1);
    	for(int i=1;i<=n;i++)
    		if(maxdis<depth[i])
    		{
    			maxdis=max(maxdis,depth[i]);
    			maxdisroot=i;
    		}
    	//以maxdisroot为根节点 寻找最长路径 
    	memset(depth,0,sizeof(depth));//清空 
    	dfs(maxdisroot,-1);
    	for(int i=1;i<=n;i++)
    		maxdis=max(maxdis,depth[i]);
    	cout<<maxdis;
    	return 0;
    }
    

    信息

    ID
    1195
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    53
    已通过
    30
    上传者