题目描述
因为中国人口众多，公共交通就显得很重要. 在传统城市公共交通系统中，公交车是一种很重要的工具。甚至现在还扮演了一种极其重要的角色。
X市的公交系统显得很独特。不像别的城市，该市公交系统是基于两站间的距离来计费的。下表描述了两站之间距离与费用的关系：
|
距离 |
费用 |
|
0<dist<=L1 |
C1 |
|
L1<dist<=L2 |
C2 |
|
L2<dist<=L3 |
C3 |
|
L3<dist<=L4 |
C4 |
|
dist>L4 |
没有这种票 |
表1
你的邻居是一位出名的吝啬鬼。他希望你能帮他计算出他列出表中两站间的最短花费，你能帮帮他吗？
为了简化这个问题，你可以假设所有的站都在一条直线上。我们仅用X坐标来描述每一个站的位置。
输入
输入文件包含多组数据。第一行包含一个整数T表示T组测试数据(T<=20)
每组数据第一行为8个数：L1, L2, L3, L4, C1, C2, C3, C4，每一个数都是不超过1,000,000,000的非负数，并且L1<=L2<=L3<=L4.
接下来两个整数n和m，表示n个站和m个询问。下面n行，每行一个数表示第i个站的x坐标。
下面m行，每行两个数表示询问的起点站和目标站。
在所有的询问中，起点站和目标站都不同。
对于每组数据有，2<=N<=100,0<=M<=500，每一个x坐标在-1,000,000,000 到1,000,000,000之间，并且没有两个x坐标相同。
输出
对于第T组测试数据第一行输出“Case T:”(没有引号）
对于每组询问，如果两个站可达，输出最小花费，否则输出“Station X and station Y are not attainable.”（没有引号）具体格式见样例。
样例输入
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
样例输出
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.
简单的最短路问题
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const long long inf=999999999999999; long long dis[101][101]; int n,m; long long L1,L2,L3,L4,c1,c2,c3,c4,X[101]; void init() { for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if (abs(X[i]-X[j])==0) dis[i][j]==0; else if (abs(X[i]-X[j])>0 && abs(X[i]-X[j])<=L1) dis[i][j]=c1; else if (abs(X[i]-X[j])>L1 && abs(X[i]-X[j])<=L2) dis[i][j]=c2; else if (abs(X[i]-X[j])>L2 && abs(X[i]-X[j])<=L3) dis[i][j]=c3; else if (abs(X[i]-X[j])>L3 && abs(X[i]-X[j])<=L4) dis[i][j]=c4; else if (abs(X[i]-X[j])>L4) dis[i][j]=inf; } } void floyd() { for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); } int main() { int t,x,y; scanf("%d",&t); for (int k=1;k<=t;k++) { scanf("%lld %lld %lld %lld %lld %lld %lld %lld",&L1,&L2,&L3,&L4,&c1,&c2,&c3,&c4); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%lld",&X[i]); init(); floyd(); printf("Case %d:\n",k); for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if (dis[x][y]<inf) printf("The minimum cost between station %d and station %d is %lld.\n",x,y,dis[x][y]); else printf("Station %d and station %d are not attainable.\n",x,y); } } return 0; }
原文：http://www.cnblogs.com/chensunrise/p/3726275.html