OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2005】希望小学

【题目描述】

地处偏僻山区的X乡有N个自然村,目前还没有一所小学,孩子们要么不上学,要么需要翻过一座大山到别处上学。如今好啦,有一位热心人士准备捐款在某个自然村建立一所希望小学。

通过调查发现,X乡各个村庄之间的道路较为复杂,有平路、上坡和下坡。考虑到每个村孩子们的人数不同,走上坡、下坡和平路的速度也不同,男孩和女孩走路速度也不同,请你为X乡选择一个最合适建立希望小学的村庄,使得所有的孩子花在路上的总时间最少。

【输入】

第1行: N B1 B2 B3 G1 G2 G3 (村庄数、男孩分别走平路、上坡、下坡每千米花费的时间以及女孩分别走平路、上坡、下坡每千米花费的时间)

第2行: Xl X2……Xn (Xi表示第i个村要上学的男孩人数)

第3行: Y1 Y2……Yn (Yi表示第i个村要上学的女孩人数)

第4行: K (道路数)

第5—K+4行: Ai Bi Si1 Si2 Si3 (村庄Ai到村庄Bi,平路Sil千米,上坡Si2千米,下坡Si3千米,i=1,2,…,K)

【输出】

T(将要建立希望小学村庄的编号)

【输入样例】

2 2 2 1 2 3 2

10 12

5 4

1 2 10 2 1

【输出样例】

2

【数据范围】

(1) N<=30, Xi<=20, Yi<=20

(2) K<=100, 每条路的长度<=30千米

(3) B1,B2,B3,G1,G2,G3为整数,都小于10个单位时间/每千米

(4) 每条道路只给出一组数据。例如:5 8 7 10 3表示从村庄5往村庄8走,平路有7千米,上坡10千米。 下坡3千米;当然也表示从村庄8往村庄5走,平路有7千米,上坡3千米。下坡10千米。

【题解】

根据条件建图,然后floyed,依次枚举其他所有村庄到某个村庄的距离,距离最小的就是答案。

建图的唯一难点就是上坡倒着走就是下坡,下坡同理,可惜题目上有提示。

【代码】

题目很水,但代码还是稍微有些冗杂。

http://paste.ubuntu.com/8128323/

评论

© OI技术宅 | Powered by LOFTER