zjh

用户名：speaksoftly

访问量：24718

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6955
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1242-网线主管（C++代码）二分
浏览：1468

你可能喜欢

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

蓝桥杯2013年第四届真题-大臣的旅费（C++代码）最短路spfa

　　作者: zjh　　　　发表时间：2019-07-15 17:14:12 浏览：631　|　评论：0　

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

![](/image_editor_upload/20190715051601_85100.jpg)

```cpp
会dfs、bfs都可以解决这个问题，只需要从任意一个结点（点A）开始，遍历所有联通的点，找到距离这个结点最远的点(点B)，然后再从B找一个距离B结点最远的点，最后得到一个最长的距离就是结果了

ps : 题目说的很明白，实际上只是一颗树，点到点的距离不存在更优，用spfa的目的是复习一波最短路，(实际是懒得写dfs、bfs (逃

#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 INF = 1e9;
const int maxn = 100010;
int n;
vector<pair<int, int> > E[maxn];	//存边、权，first边, second权
int d[maxn];		//每个点的距离
bool vis[maxn];	 //判断该点是否访问过
int Max;			//第一次保存从1号结点到任意结点的最大距离，第二次保存第一次结果的结点到任意结点的最大值
int Index = 1;	  //用于保存第一次从1号结点到其他结点距离最大值的结点下标

/** 初始化距离和判重数组 */
void init() {
	for(int i = 0; i < maxn; ++i) {
		vis[i] = false;
		d[i] = INF;	//把每个点的距离都设为无穷大
	}
}

/** 
 * spfa核心代码
 * node : 代表从当前node结点开始计算
 */
void spfa(int node) {
	init();			//初始化
	d[node] = 0;	   //node结点到node的距离为0
	queue<int> q;
	q.push(node);
	/************* 核心代码 ***************/
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		vis[now] = false;	//先把当前结点设为now，相当于回溯，因为该点可能还有其它边比当前的结果更优(实际上这道题并没有(逃
		//枚举当前结点的所有边
		for(int i = 0; i < E[now].size(); ++i) {
			int v = E[now][i].first;	//v : now结点存的边
			//如果 v 结点的距离小于当前 now 结点到 v 结点的距离，那么就更新 v 这个结点的距离
			if(d[v] > d[now] + E[now][i].second) {	//跟求最短路一样，到达每个点的距离，并且只有n - 1条边，每个点都可达，说明这是一棵树，那么到每个点直接的距离都只有一个
				d[v] = d[now] + E[now][i].second;	//松弛
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	/***********************************/
	for(int i = 1; i <= n; ++i) {
		if(d[i] > Max && d[i] != -INF) {	//获得负数最小的下表和距离，虽然题目说肯定每个点都可以直接或间接到达，但为了保险起见，还是加一个判断，表示d[i]可达
			Max = d[i];
			Index = i;
		}
	}
}

int main() {
	cin >> n;
	for(int i = 1; i < n; ++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));
	}
	spfa(1);		//从1结点开始，找1最远的那个结点
	spfa(Index);	//从最远的结点开始，找距离index这个点最远的点
	ll total = 0;
	//最后根据题意计算一下花费就结束了
	for(int i = 1; i <= Max; ++i) {
		total += i + 10;
	}
	cout << total << endl;
	return 0;
}
```

0.0分

6 人评分

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

zjh

TA的其他文章

你可能喜欢

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

汽水瓶（C++代码）

C语言训练-字符串正反连接（C语言代码）

C二级辅导-等差数列（C语言代码）

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

蓝桥杯2013年第四届真题-大臣的旅费（C++代码）最短路spfa

评论区

精彩推荐

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

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

剪刀石头布（C语言代码）

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

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

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

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

1012题解

字符串比较（C语言代码）

小O的数字（C语言代码）

zjh

TA的其他文章

你可能喜欢

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

汽水瓶 （C++代码）

C语言训练-字符串正反连接 （C语言代码）

C二级辅导-等差数列 （C语言代码）

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

蓝桥杯2013年第四届真题-大臣的旅费 （C++代码）最短路spfa

评论区

精彩推荐

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

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

剪刀石头布 （C语言代码）

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

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

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

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

1012题解

字符串比较 （C语言代码）

小O的数字 （C语言代码）

汽水瓶（C++代码）

C语言训练-字符串正反连接（C语言代码）

C二级辅导-等差数列（C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费（C++代码）最短路spfa

　　评论区

剪刀石头布（C语言代码）

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

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

字符串比较（C语言代码）

小O的数字（C语言代码）