#301. 最优高铁环

最优高铁环

题目描述

由于该国地形起伏不平,各地铁路的适宜运行速度不同。因此该国的每一条行车路线都由K列车次构成。例如:K=5的一条路线为:T120-D135-S1-G12-K856。当某一条路线的末尾车次与另一条路线的开头车次相同时,这两条路线可以连接起来变为一条更长的行车路线。显然若干条路线连接起来有可能构成一个环。

若有3条行车路线分别为: x1-x2-x3 x3-x4 x4-x5-x1 x1~x5车次的速度分别为v1~v5 定义高铁环的值为(环上各条行车路线速度和)的平均值,即: [(v1+v2+v3)+(v3+v4)+(v4+v5+v1)]/3. 所有高铁环的值的最大值称为最优高铁环的值。 给出M条行车路线,求最优高铁环的值。

输入格式

第一行为行车路线条数M 接下来M行每行一条行车路线,由若干车次构成,各车次之间用'-'号隔开,车次的标号方式如上所述。 数据保证输入的合法性。

输出格式

最优高铁环的值。四舍五入到最接近的整数。 若不存在这样的环,输出-1.

样例输入

3
T120-D135-S1
S1-G12
G12-K856-T120

样例输出

1283

提示

样例解释: [(200+300+1000)+(1000+500)+(500+150+200)]/3=1283

数据范围: 50%的数据:0<M<=1000 100%的数据,0<M<=50000 每条行车路线车次个数不超过20.

输入数据较大,请使用read和scanf。数据不保证使用cin者不超时。 为避免精度问题,请使用double类型。 数据保证结果不超过2147483647.