1182: 公交车站
题目描述
CS市有一条笔直的干道 ， 干道上有 N 个公交车站，第i个公交车站的位置为 xi , 公交车在公交车站之间来回行驶 （乘客只能在公交车站上下车）。公交车有个里程表，如下图所示(比如说 a b两站之间的距离为 0<dist<=L1,那么乘客从 a 到b需要花费 C1元):
PIPI是个精明的人，他总是想用最便宜的价格从起点坐车到终点，你能告诉PIPI从某个起点 s 到终点 t的最小花费是多少吗??
输入
输入第一行包含测试用例组数 T。
对于每一组样例，第一行包括8个正整数 L1~L4 ， C1~C4。
接下来两个正整数 N 和 M，代表公交站的个数和PIPI询问的次数。 (N<=500,M<=100000)。
接下来N行每行包括一个整数代表公交车站的位置。
接下来M行每行包括两个整数 s 和 t,代表PIPI询问的起点车站编号和终点车站编号 ( 1<=s,t <=N)。
输出
对于每组样例，首先输出Case数，然后对于每一次询问，若PIPI能从s到t，输出其最小花费。若不能从 s到t，输出"Station s and station t 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.
思路
计算每个站点之间的花费，然后跑一次 floyed 算法。
#include<bits/stdc++.h>
using namespace std;
const int Inf = 0x3f3f3f3f;
const int N = 505;
int gra[N][N];
int loc[N];
int main()
{
// freopen("in.cpp", "r", stdin);int T, l[4], c[4], n, m, s, t, dis;scanf("%d", &T);for(int cse = 1; cse <= T; cse++){
for(int i = 0; i < 4; i++)scanf("%d", &l[i]);for(int i = 0; i < 4; i++)scanf("%d", &c[i]);scanf("%d%d", &n, &m);for(int i = 0; i < n; i++)scanf("%d", &loc[i]);for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
gra[i][j] = gra[j][i] = Inf;dis = abs(loc[i] - loc[j]);if(dis == 0)gra[i][j] = gra[j][i] = 0;else if(dis <= l[0])gra[i][j] = gra[j][i] = c[0];else if(dis <= l[1])gra[i][j] = gra[j][i] = c[1];else if(dis <= l[2])gra[i][j] = gra[j][i] = c[2];else if(dis <= l[3])gra[i][j] = gra[j][i] = c[3];elsegra[i][j] = gra[j][i] = Inf;}}// floyedfor(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
if(gra[j][k] > gra[j][i] + gra[i][k])gra[j][k] = gra[j][i] + gra[i][k];}}}
// for(int i = 0; i < n; i++)
// {
// for(int j = 0; j <n; j++)
// printf("%3d", gra[i][j]);
// printf("\n");
// }printf("Case %d:\n", cse);for(int i = 0; i < m; i++){
scanf("%d%d", &s, &t); --s, --t;if(gra[s][t] != Inf)printf("The minimum cost between station %d and station %d is %d.\n", s + 1, t + 1, gra[s][t]);elseprintf("Station %d and station %d are not attainable.\n", s + 1, t + 1);}}return 0;
}