TimeLimit: 2000/1000 MS (Java/Others) Memory Limit:32768/32768 K (Java/Others)Total Submission(s): 9738 Accepted Submission(s): 2653
ProblemDescription
Becauseof the huge population of China, public transportation is very important. Busis an important transportation method in traditional public transportationsystem. And it’s still playing an important role even now.The bus system of City X is quite strange. Unlike other city’s system, the costof ticket is calculated based on the distance between the two stations. Here isa list which describes the relationship between the distance and the cost.
Your neighbor is a person who is a really miser. He asked you to help him tocalculate the minimum cost between the two stations he listed. Can you solvethis problem for him?To simplify this problem, you can assume that all the stations are located on astraight line. We use x-coordinates to describe the stations’ positions.
Input
The input consists of several test cases.There is a single number above all, the number of cases. There are no more than20 cases.Each case contains eight integers on the first line, which are L1, L2, L3, L4,C1, C2, C3, C4, each number is non-negative and not larger than 1,000,000,000.You can also assume that L1<=L2<=L3<=L4.Two integers, n and m, are given next, representing the number of the stationsand questions. Each of the next n lines contains one integer, representing thex-coordinate of the ith station. Each of the next m lines contains twointegers, representing the start point and the destination.In all of the questions, the start point will be different from thedestination.For each case,2<=N<=100,0<=M<=500, each x-coordinate is between-1,000,000,000 and 1,000,000,000, and no two x-coordinates will have the samevalue.
Output
For each question, if the two stations areattainable, print the minimum cost between them. Otherwise, print “Station Xand station Y are not attainable.” Use the format in the sample.
SampleInput
2
1 2 3 41 3 5 7
4 2
1
2
3
4
1 4
4 1
1 2 3 41 3 5 7
4 1
1
2
3
10
1 4
SampleOutput
Case 1:
Theminimum cost between station 1 and station 4 is 3.
Theminimum cost between station 4 and station 1 is 3.
Case 2:
Station1 and station 4 are not attainable.
Source
2008“Sunline Cup” National Invitational Contest
Recommend
wangye | We havecarefully selected several similar problems for you: 1874 2722 1596 2066 1385
算法分析：
首先，多起点多终点，数据范围小，floyed算法，而后无限wrong，开始改，数据范围，从long long 到 int 64，该INF值，结果就是不对，最后竟然因为case少加了个冒号，憋人啊。
代码实现：
#include<bits/stdc++.h> #define INF 0x3f7f7f7f7f7f7f7f using namespace std; long long int mp[150][150]; long long int l[5],c[5]; long long dis(long long d) { if(d==0) return 0; for(int j=0;j<=3;j++) if(d<=l[j+1]&&d>l[j]) { return c[j+1]; } return INF; } int main() { long long int T,t=0; scanf("%lld",&T); while(T--) { t++; for(int i=1;i<=4;i++) scanf("%lld",&l[i]); l[0]=0; for(int i=1;i<=4;i++) scanf("%lld",&c[i]); long long int n,q; scanf("%lld%lld",&n,&q); for (int i=1;i<=n;i++) for(int j=i;j<=n;j++) mp[i][j]=INF; long long int x[105]; for(int i=1;i<=n;i++) { scanf("%lld",&x[i]); } for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { mp[j][i]=mp[i][j]=dis(abs(x[j]-x[i])); } } for(int k=1;k<=n;k++)//floyed算法 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i!=k&&j!=i&&j!=k&&mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j]; } printf("Case %lld:\n",t);//这里少个: for(int i=1;i<=q;i++) { long long int a,b; scanf("%lld%lld",&a,&b); if(mp[a][b]<INF) printf("The minimum cost between station %lld and station %lld is %lld.\n",a,b,mp[a][b]); else printf("Station %lld and station %lld are not attainable.\n",a,b); } } return 0; }
