1182: 公交车站
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 868 Solved: 325
[Submit] [Status] [Web Board] [Creator:]
Description
CS市有一条笔直的干道 ， 干道上有 N 个公交车站，第i个公交车站的位置为 xi , 公交车在公交车站之间来回行驶 （乘客只能在公交车站上下车）。公交车有个里程表，如下图所示(比如说 a b两站之间的距离为 0<dist<=L1,那么乘客从 a 到b需要花费 C1元):
PIPI是个精明的人，他总是想用最便宜的价格从起点坐车到终点，你能告诉PIPI从某个起点 s 到终点 t的最小花费是多少吗??
Input
输入第一行包含测试用例组数 T。
对于每一组样例，第一行包括8个正整数 L1~L4 ， C1~C4。
接下来两个正整数 N 和 M，代表公交站的个数和PIPI询问的次数。 (N<=500,M<=100000)。
接下来N行每行包括一个整数代表公交车站的位置。
接下来M行每行包括两个整数 s 和 t,代表PIPI询问的起点车站编号和终点车站编号 ( 1<=s,t <=N)。
对于每一组样例，第一行包括8个正整数 L1~L4 ， C1~C4。
接下来两个正整数 N 和 M，代表公交站的个数和PIPI询问的次数。 (N<=500,M<=100000)。
接下来N行每行包括一个整数代表公交车站的位置。
接下来M行每行包括两个整数 s 和 t,代表PIPI询问的起点车站编号和终点车站编号 ( 1<=s,t <=N)。
Output
对于每组样例，首先输出Case数，然后对于每一次询问，若PIPI能从s到t，输出其最小花费。若不能从 s到t，输出"Station s and station t are not attainable."。详情请见样例输出。
Sample Input
2
1 2 3 4 1 3 5 7
4 2
1
2
3
4
1 4
4 1
1 2 3 4 1 3 5 7
4 1
1
2
3
10
1 4
Sample Output
Case 1:
The minimum cost between station 1 and station 4 is 3.
The minimum cost between station 4 and station 1 is 3.
Case 2:
Station 1 and station 4 are not attainable.