1075. [SCOI2007]最优驾车drive
#1075. [SCOI2007]最优驾车drive
题目描述
有n条南北方向的双向街道和n条东西方向的双向街道纵横交错。相邻街道（不管是哪个走向）的距离均为L英
里。西南角交叉口的坐标为(1,1)，东北角为(n,n)。在所有交叉口均可任意改变行驶方向。每条街道有它自己的最
高速度限制，该限制对整条街道有效（不管行驶方向如何）。你的任务是从交叉口(xs,ys)开车行驶到(xt,yt)，要
求只能在交叉口处改变速度，行驶过程中不得违反所在街道的速度限制，只能沿着路程最短的线路行驶，并且行驶
时间在给定的闭区间[t1,t2]内。车速以"每小时英里数"为单位，它必须是5的正整数倍。若车速为v，则每加仑
汽油能行驶的英里数为80-0.03v2。
输入格式
输入第一行为两个整数n, L, 第二行包含n个正整数，从南到北描述n条东西走向的街道的速度限制，第三行包
含n个正整数，从西到东描述n条南北走向的街道的速度限制。第四行包含六个正整数xs, ys, xt, yt, t1, t2.
输出格式
如果无解，输出No，否则输出两行，分别描述最早到达的方案（若有多种方案，选择其中最省油的）和最省油
的方案（如果有多种方案，选择其中最早到达的）。每种方案用两个数表示，第一个数表示到达时刻（单位：分钟
，向上取整）；第二个数表示耗油量（单位：加仑，四舍五入保留两位小数）。
样例
样例输入
【样例输入1】
6 20
30 40 50 50 50 50
50 50 50 50 50 40
1 1 6 6 300 320
【样例输入2】
8 2
10 20 20 30 10 20 10 10
10 20 20 30 10 20 10 20
6 8 2 4 10 39
样例输出
【样例输出1】
300 6.25
318 5.60
【样例输出2】
No
【样例说明】样例1的最快路线为以40英里/小时为速度匀速前进，路程为200英里，因此时间为5小时，每加仑
汽油可以行驶80-0.03*40*40=32英里，因此耗油量为200/32=6.25加仑。最省油路线是先以40英里/小时行驶120英
里，然后以35英里/小时行驶80英里，耗油量为120/32+80/(80-0.03*35*35)=5.60加仑。下图的路线可以同时满足
两种方案（其中第二种方案需要在(6,2)处改变速度）。【限制】100%的数据满足：1<=n<=10, 1<=l<=20, 0<=t1<=
t2<=1000. 速度限制不超过50
2015.03.13另加数据.