zjh

```cpp
#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int INF = 1e9;
//priority_queue<int, vector<int>, greater<int> > q;
vector<pair<int, int> > E[maxn];	//存图, E[x].first : 边y, E[x].second : 边权
int n, node, cnt;	  //n : 输入, node : 记录从当前点能到达的最长一个点的编号, cnt : 用于dfs比较边权
bool vis[maxn];		//判重数组

/**
 * dfs : 第一次dfs从结点1开始，找到一条距离结点1最远的点，第二次dfs从找到的点开始，寻找距离这个点最远的点就是答案
 * v : 当前结点
 * k : 达到该点权值的总和
 */
void dfs(int v, int k) {
	if(k > cnt) {	//更新状态
		cnt = k;	 //权值总和
		node = v;	//该点编号
	}
	//枚举该点所有边
	for(int i = 0; i < E[v].size(); ++i) {
		if(!vis[E[v][i].first]) {	//没访问过的点都进行一次dfs
			vis[E[v][i].first] = true;	 //标记
			//递归枚举E[v][i].first的边，权值总和更新
			dfs(E[v][i].first, k + E[v][i].second);
			vis[E[v][i].first] = false;	//回溯
		}
	}
}
int main() {
	cin >> n;
	for(int i = 0; i < n - 1; ++i) {
		int x, y, z;
		cin >> x >> y >> z;
		//建立无向图
		E[x].push_back(make_pair(y, z));
		E[y].push_back(make_pair(x, z));
	}
	//从结点1开始找一个距离结点1最远的点
	vis[1] = true;
	dfs(1, 0);
	vis[1] = false;
	//找到最远的点之后，cnt置0，从这个结点开始早距离它最远的点，最后答案就是cnt
	cnt = 0;
	vis[node] = true;
	dfs(node, 0);
	int res = 0;
	//(1km = 1 + 10), (2km = 1km + 2 + 10), (3km = 2km + 3 + 10).......
	for(int i = 1; i <= cnt; ++i) {
		res += i + 10;
	}
	cout << res << endl;
	return 0;
}
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

C语言训练-计算t=1+1/2+1/3+...+1/n （C语言代码）

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

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-亲密数（C++代码）

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

蓝桥杯2013年第四届真题-大臣的旅费（C++代码）补上dfs解法

评论区

精彩推荐

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

Minesweeper （C语言代码）

IP判断（C语言代码）

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

简单的a+b （C语言代码）

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

最小公倍数（C语言代码）

printf基础练习2 （C语言代码）

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

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

zjh