2515 - 计算路费

题目描述

A 国国王是一个非常精明的人,聪明的他发现,他的国家有 n 个城市(城市编号为 1 \sim n),如果要使得城市之间互相可达,只要修 n-1 条道路,虽然某些城市不能直接可达,但经过一些其他的城市,也是能到的,于是他真的给自己的国家修建了 n-1 条高速公路,且使得高速公路能连接到所有的城市。

比如:城市 1 和城市 2 之间修建了双向高速公路,城市 2 和城市 3 之间修建了双向高速公路,那么虽然城市 1 和城市 3 之间并没有修建公路,但经过城市 2 也能实现城市 1 的人能够到达城市 3

他制定了高速公路的收费方法:从第 L-1 公里到第 L 公里的这部分路程,收费金额为 L+10 元。

也就是说,第 0 公里到 1 公里收费金额 = 1+10=11 元,第 12 公里收费金额 = 2+10=12 元,那么如果走过 2 公里的高速公路,总收费 = 11+12=23 元。

请问:如果在该王国的任意城市出发,到另一个任意城市结束,中途不下高速公路,且走过的高速公路或者城市不会重复的走;请问,最多要支付多少元的路费?

输入

1 行有一个整数 n ,代表城市数量;

接下来 n-1 行,每行有 3 个整数,x y len,代表了从 x 号城市到 y 号城市之间存在一条双向的高速公路,公路的长度为 len 公里。

输出

输出一个整数,代表了最多可能支付的高速公路的费用。

样例

输入

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

输出

135
说明

【数据规模】

1≤n≤100001≤len≤100

【样例说明】

在该图中,从 4 号城市到 5 号城市,总路长为 9 公里,需要支付的费用 = 11+12+13+14+15+16+17+18+19 = 135 元,这是本样例中可能产生的最高的路费。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 109
通过人数 59
金币数量 2 枚
难度 基础


上一题 下一题