【每日一题】问题 1438: 大臣的旅费(本题为蓝桥真题,较难)

题目描述

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

输入

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

输出

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

样例输入

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

样例输出

135

原文发布于微信公众号 - 编程范(dotcpp)

原文发表时间:2018-05-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端儿

数数

我们平时数数都是喜欢从左向右数的,但是我们的小白同学最近听说德国人数数和我们有些不同,他们正好和我们相反,是从右向左数的。因此当他看到123时会说“321”。

1083
来自专栏数据派THU

Python能让你上天?带你挖掘隐藏彩蛋~(附代码)

4344
来自专栏数据结构与算法

1722 最优乘车 1997年NOI全国竞赛

1722 最优乘车 1997年NOI全国竞赛  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解 题目描述 Des...

3195
来自专栏数据结构与算法

洛谷P2234 [HNOI2002]营业额统计(01Tire树)

题目描述 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本,账本上记录了...

2509
来自专栏Python攻城狮

Python之禅

在Python交互式解释器中输 入import this就会显示Tim Peters的The Zen of python

931
来自专栏数据结构与算法

3315 时空跳跃者的魔法

3315 时空跳跃者的魔法 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 白银 Silver 题目描述 Description ...

39210
来自专栏PPV课数据科学社区

趣文 | 程序员们,都进来看看编程语言之父都有谁

1、PHP PHP之父,Rasmus Lerdorf,1994年,为了要维护个人网页而制作的一个简单的用Perl语言编写的程序。这些工具程序用来显示 Rasmu...

3507
来自专栏Crossin的编程教室

【每周一坑】黑色星期五

今天的题目跟西方的传说有关 ? “黑色星期五”这个词对于爱购物的人来说并不陌生,它是美国人民的购物狂欢日,堪比中国的双十一、双十二。 但其实“黑色星期五”在西方...

2967
来自专栏小狼的世界

Pandas 快速入门(二)

我们在进行数据处理时,拿到的数据可能不符合我们的要求。有很多种情况,包括部分数据缺失,一些数据的格式不正确,一些数据的标注问题等等。对于这些数据,我们在开始分析...

1442
来自专栏数据科学

股票实时流计算

var element = $('#61901593-c697-4e0e-ad17-c8f2c3fae6ae'); {"model_id": "8629...

1484

扫码关注云+社区

领取腾讯云代金券