蓝桥杯题目——大臣的旅费

标签: 蓝桥杯题目练习  算法  dfs  数据结构

蓝桥杯试题 大臣的旅费

问题描述

很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。
为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋,用于存放往来城市间的路费。
聪明的J发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关,在走第x千米到第x+1千米这一千米中(x是整数),他花费的路费是x+10这么多。
也就是说走1千米花费11,走2千米要花费23。
J大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?

输入

输入的第一行包含一个整数n,表示包括首都在内的T王国的城市数(n<=10000)
城市从1开始依次编号,1号城市为首都。
接下来n-1行,描述T国的高速路(T国的高速路一定是n-1条)
每行三个整数Pi, Qi, Di,表示城市Pi和城市Qi之间有一条高速路,长度为Di千米。(Di<=1000)

输出

输出一个整数,表示大臣J最多花费的路费是多少。

样例输入

5
1 2 2
1 3 1
2 4 5
2 5 4

样例输出

135

题目分析

题目大意:给一个带权值的无环图,然后在图中找出距离最远的两个节点之间的距离。求出该距离之后计算相应的旅费。
旅费计算方式:在走第x千米到第x+1千米这一千米中(x是整数),他花费的路费是x+10这么多。 即从第1千米到第2千米的路费是1+10=11,第2千米到第3千米是2+10=12;以此类推。
因此走1千米的总路费为11,总2千米的总路费为11+12=23,走3千米的总路费为11+12+13=36,以此类推。

求两点间最大路径分析:
以题目给出的5个城市为例,可画出如下树图:
在这里插入图片描述
树的直径解法
树的直径是指树上距离最远的两点间的距离(显然这个树的边须为带权边),它在树上问题上有许多应用,往往通过树的直径的性质可以将一个高时间复杂度的解法变为线性求解。
树的直径算法主要有两个,下面给出利用两次DFS(或BFS)求树的直径算法的做法:
1.从任意节点出发,通过DFS(或BFS)对树进行一次遍历,求出与出发点距离最远的节点记为p;
2.从节点p出发,通过DFS(或DFS)再进行一次遍历,求出与p距离最远的节点,记为q
则从p到q的路径就是树的一条直径

具体介绍看博客:https://blog.csdn.net/the_ZED/article/details/104174375?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param

代码:

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

const int MAX=10010;		//预设的最多城市数
int maxFarNode;				//maxFarNode存放的是从指定节点出发所能到的最远节点
int maxLen=-1;				//maxLen用于指示从指定节点出发所能到的最远距离
bool vis[MAX];				//用于指示某个点是否被访问过 
struct Node{				// 利用结构体来存放一个点的子节点及边的权值 
	int child,length;
	Node(int a,int b){
		child=a,length=b;
	}
};
vector<Node> v[MAX];		//利用容器来存放,相当于一个动态的二维数组
							// 即链式存储,邻接表 
void dfs(int node,int nowLen)
{
	if(vis[node]) return;
	vis[node]=true;
	for(int i=0;i<v[node].size();i++)
	{
		int child =v[node][i].child;  // 与node相连的第i个结点个结点名称 
		int length=v[node][i].length; // 与node相连的第i个结点的边的权值 
		if(vis[child]) continue;      // 如果该结点已经被访问过则跳过该次循环 
		if(nowLen+length > maxLen){
			maxLen = nowLen+length;			//更新最大值 
			maxFarNode = child;				//更新最大值所在的节点位置 
		}
		dfs(child,nowLen+length); 
	}
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,len;
		cin>>x>>y>>len;
		v[x].push_back(Node(y,len));
		v[y].push_back(Node(x,len));
	}
	dfs(1,0);
	memset(vis,false,sizeof(vis));
	maxLen=-1;
	dfs(maxFarNode,0);
	cout<<(maxLen*10+maxLen*(1+maxLen)/2)<<endl;
	return 0;
}

版权声明:本文为Ace_bb原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Ace_bb/article/details/107745938

智能推荐

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

猜你喜欢

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...

springboot 过滤器Filter vs 拦截器Interceptor 详解

1 前言       最近接触到了过滤器和拦截器,网上查了查资料,这里记录一下,这篇文章就来仔细剖析下过滤器和拦截器的区别与联系。 2 拦截器与过滤器之间的区别 从上面对拦截器与过滤器的描述来看,它俩是非常相似的,都能对客户端发来的请求进行处理,它们的区别如下: 作用域不同 过滤器依赖于servlet容器,只能在 servlet容器,web环境下使用 拦截器依赖于sp...

IDEA环境--JavaWeb项目【分页功能实现】

参考链接:https://www.jianshu.com/p/d108d0cd9acf 1、前言 最近在写一些项目,遇到要使用分页功能的地方,就简单的学习了一下,在此总结一下具体实现的过程以及遇到的问题。 分页功能:当我们写一下web项目时会遇到一个页面要显示很多数据,一下子都显示出来效率会很低,也不美观。这就要用到分页,其作用也就是将数据分割成多个页面来进行显示。 2、项目介绍 这只是一个简单的...

517【毕设课设】基于单片机仓库家庭防火防盗报警系统

【资源下载】下载地址如下: https://docs.qq.com/doc/DTlRSd01BZXNpRUxl 功能简要说明: 1.51单片机+1602液晶+按键+烟雾检测传感器MQ+红外检测+蜂鸣器+DHT11温湿度传感器; 2.按键设置烟雾报警浓度值,温度报警值; 3.当达到报警条件,蜂鸣器响; 5.电路板为PCB腐蚀所做,图文件为altiumdesigner工程文件。 6.程序采用C语言编写...