问题 U: 最优高铁环
内存限制:128 MB
时间限制:3.000 S
评测方式:文本比较
命题人:
提交:15
解决:5
题目描述
幻影国建成了当今世界上最先进的高铁,该国高铁分为以下几类:
- S---高速光子动力列车---时速1000km/h
- G---高速动车---时速500km/h
- D---动车组---时速300km/h
- T---特快---时速200km/h
- K---快速---时速150km/h
该国列车车次标号由上述字母开头,后面跟着一个正整数(≤1000)(\leq 1000)(≤1000)构成。
由于该国地形起伏不平,各地铁路的适宜运行速度不同。因此该国的每一条行车路线都由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条行车路线,求最优高铁环的值。
x1−x2−x3
x3−x4
x4−x5−x1
x1∼x5车次的速度分别为v1 ∼v5
定义高铁环的值为(环上各条行车路线速度和)的平均值,即:
((v1+v2+v3)+(v3+v4)+(v4+v5+v1))/3
所有高铁环的值的最大值称为最优高铁环的值。
给出M条行车路线,求最优高铁环的值。
输入
第一行为行车路线条数M
接下来M行每行一条行车路线,由若干车次构成,各车次之间用'-'号隔开,车次的标号方式如上所述。
数据保证输入的合法性。
接下来M行每行一条行车路线,由若干车次构成,各车次之间用'-'号隔开,车次的标号方式如上所述。
数据保证输入的合法性。
输出
最优高铁环的值。四舍五入到最接近的整数。
若不存在这样的环,输出-1.
若不存在这样的环,输出-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.
50%的数据:0<M≤1000
100%的数据,0<M≤50000
每条行车路线车次个数不超过20.
输入数据较大,请使用read和scanf。数据不保证使用cin者不超时。
为避免精度问题,请使用double类型。
数据保证结果不超过2147483647.