李达

用户名：lida1

访问量：9883

签　名：

等　　级
排　　名	1043
经　　验	3152
参赛次数	5
文章发表	10
年　　龄	0
在职情况	学生
学　　校	信阳农林学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）官方题解
浏览：364

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）官方题解

　　作者: 李达　　　　发表时间：2020-07-25 11:45:58 浏览：364　|　评论：2　

原题链接：蓝桥杯2013年第四届真题-大臣的旅费

# 两遍dfs求即可，裸体遍历图模板

**
1.使用vector用来存图；
2.两边dfs遍历两遍，第一次找根到最远距离，第二次找最远距离（第一次）到最远距离
3.dfs遍历图就行了
4.维护最大值
5.循环求等差数列即可
**
```c
#include <bits/stdc++.h>
using namespace std;
int n,p,q,d,ans;

struct T{
	int v,w;
};
int pnt=-1;
void dfs(vector<T> m[],int vis[],int start,int dis){
	vector<T>nei_i=m[start];
	vis[start]=0;
	bool isleaf=true;
	for(int k=0;k<nei_i.size();k++){
		int num=nei_i[k].v;
		if(vis[num]==-1){
			isleaf=false;
		   dfs(m,vis,num,dis+nei_i[k].w);  	
		}
		
	}
	vis[start]=-1;
	if(isleaf){
		if(dis>ans){
			ans=dis;
			pnt=start;
		}
	}
}
int main()
{
    cin>>n;
	vector<T> m[n+1];
	int vis[n+1];
	memset(vis,-1,sizeof(vis));
    for(int i=0;i<n-1;i++){
    	T a,b;
    	cin>>p>>q>>d;
    	a.v=p;
    	a.w=d;
    	b.v=q;
    	b.w=d;
    	m[p].push_back(b);
    	m[q].push_back(a);
	}
	dfs(m,vis,1,0);
	ans=0;
	dfs(m,vis,pnt,0);
	//printf("%d\n",ans);
	int sum=0,cnt=11;
	
	for(int i=0;i<ans;i++){
		sum+=cnt;
		cnt++;
		//printf("%d\n",sum);
	}
	printf("%d",sum);
    return 0;
}

```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

pingfan443

牛逼6666

2020-10-16 16:44:41

hui

2020-10-16 16:44:10

李达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

用筛法求之N内的素数。（C语言代码）

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）官方题解

评论区

精彩推荐

C二级辅导-计负均正（C语言代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

妹子杀手的故事（C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

程序员的表白（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

李达

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解（C++代码）官方题解

评论区

精彩推荐

C二级辅导-计负均正 （C语言代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言训练-角谷猜想 （C++代码）（3N+1问题）

妹子杀手的故事 （C语言代码）

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

数组输出 （C语言代码）--此题的题目描述有问题

程序员的表白 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

用筛法求之N内的素数。（C语言代码）

用筛法求之N内的素数。（C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

【蟠桃记】（C语言代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

妹子杀手的故事（C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

数组输出（C语言代码）--此题的题目描述有问题

程序员的表白（C语言代码）