此题用floyd最好，因为是任意两点！！！纠结啊，因为范围问题一直Compilation Error 后来范围定了一直超时，最后才发现晕的把函数放到循环里面了，这不影响结果，可是严重超时！！！
The bus system of City X is quite strange. Unlike other city’s system, the cost of ticket is calculated based on the distance between the two stations. Here is a 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 to calculate the minimum cost between the two stations he listed. Can you solve this problem for him?
To simplify this problem, you can assume that all the stations are located on a straight line. We use x-coordinates to describe the stations’ positions.
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 stations and questions. Each of the next n lines contains one integer, representing the x-coordinate of the ith station. Each of the next m lines contains two integers, representing the start
point and the destination.
In all of the questions, the start point will be different from the destination.
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 same value.
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<stdio.h>
#include<string.h>
#define data 99999999999LL////注意！要加LL，不然会报错数据太大
long long map[105][105];//应该用long long型
int arr[105];
int L1, L2, L3, L4, C1, C2, C3, C4,d;
int n1,m1;
long long int jz(int t)
{
if(t==0)return 0;
else if(t<=L1)return C1;
else if(t<=L2)return C2;
else if(t<=L3)return C3;
else if(t<=L4)return C4;
else return data;
}
void floyd()
{
for(int k=1;k<=n1;k++)
for(int i=1;i<=n1;i++)
for(int j=1;j<=n1;j++)
if (map[i][j] > map[i][k]+map[k][j])
map[i][j] =map[i][k]+map[k][j];
}
int main()
{
int n,i,j,flag=0,a,b;
scanf("%d",&n);
while(n--)
{
memset(arr,0,sizeof(arr));
scanf("%d%d%d%d%d%d%d%d",&L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);
scanf("%d%d",&n1,&m1);
for(i=1;i<=n1;i++)
scanf("%d",&arr[i]);
for(i = 1; i <= n1; i++)
for(j = 1; j <= n1; j++)
if(i == j) map[i][j] = 0;
else map[i][j] =data;
for(i=1;i<=n1;i++)
{
for(j=i+1;j<=n1;j++)
{
d=arr[i]-arr[j];
if(d<0)d=-d;
map[i][j]=map[j][i]=jz(d);
}
}
floyd();//刚开始把函数放到了下面while循环里面，超时n次
flag++;
printf("Case %d:\n",flag);//易错点，注意显示
for(i=1;i<=m1;i++)
{
scanf("%d%d",&a,&b);
if(map[a][b]!=data)
printf("The minimum cost between station %d and station %d is %I64d.\n",a,b,map[a][b]);
else
printf("Station %d and station %d are not attainable.\n",a,b);
}
}
return 0;
}
下面是别人比较清晰的代码，函数调用
：：
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <cmath>
using namespace std;
const long long INF = 99999999999LL; //注意！要加LL，不然会报错数据太大
const int N = 105;
int l1, l2, l3, l4, c1, c2, c3, c4;
long long map[N][N]; //距离可能会爆int，所以用long long
int place[N];
int n, m;
void init()
{
int i, j;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(i == j) map[i][j] = 0;
else map[i][j] = INF;
}
void input()
{
int i, j, len;
scanf("%d%d%d%d%d%d%d%d", &l1, &l2, &l3, &l4, &c1, &c2, &c3, &c4);
scanf("%d %d", &n, &m);
init();
for(i = 1; i <= n; i++)
{
scanf("%d", &place[i]);
}
for(i = 1; i <= n; i++)
{
for(j = i+1; j <= n; j++)
{
len = abs(place[i] - place[j]);
if(0 < len && len <= l1) map[i][j] = map[j][i] = c1;
else if(l1 < len && len <= l2) map[i][j] = map[j][i] = c2;
else if(l2 < len && len <= l3) map[i][j] = map[j][i] = c3;
else if(l3 < len && len <= l4) map[i][j] = map[j][i] = c4;
}
}
}
void floyd() //这题绝对是用floyd方便
{
int i, j, k;
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
if(map[i][j] > map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
}
void output()
{
int ti, tj;
static int zz = 1;
printf("Case %d:\n", zz++);
while(m--)
{
scanf("%d %d", &ti, &tj);
if(map[ti][tj] != INF)
printf("The minimum cost between station %d and station %d is %I64d.\n", ti, tj, map[ti][tj]);
else
printf("Station %d and station %d are not attainable.\n", ti, tj);
}
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
input();
floyd();
output();
}
return 0;
}
从网上找的比较好的想法，直接标记-1http://archive.cnblogs.com/a/2190532/
代码如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long long int L1,L2,L3,L4,C1,C2,C3,C4;
long long int f[110][110],d[110];
int main()
{
int i,j,k,N,M,t,tt,a,b;
long long int temp;
scanf("%d",&t);
for(tt=0;tt<t;tt++)
{
scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",
&L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%I64d",&d[i]);
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if(i==j)
f[i][j]=0;
else
{
temp=abs(d[i]-d[j]);
if(temp<=L1)
f[i][j]=C1;
else if(temp>L1&&temp<=L2)
f[i][j]=C2;
else if(temp>L2&&temp<=L3)
f[i][j]=C3;
else if(temp>L3&&temp<=L4)
f[i][j]=C4;
else
f[i][j]=-1;
}
}
for(k=0;k<N;k++)
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(f[i][k]!=-1&&f[k][j]!=-1)
{
temp=f[i][k]+f[k][j];
if(temp<f[i][j]||f[i][j]==-1)
f[i][j]=temp;
}
printf("Case %d:\n",tt+1);
for(i=0;i<M;i++)
{
scanf("%d%d",&a,&b);
if(f[a-1][b-1]==-1)
printf("Station %d and station %d are not attainable.\n",a,b);
else
printf("The minimum cost between station %d and station %d is %I64d.\n",a,b,f[a-1][b-1]);
}
}
return 0;
}
#include<stdio.h>
#include<math.h>
__int64 p[105],d[105][105];
int main()
{
int t,tt,n,m,a,b,i,j,k;
__int64 L1,L2,L3,L4,C1,C2,C3,C4,temp;
scanf("%d",&t); // 居然是少写了这句，所以t成了随机数，编译通过了
for(tt = 1; tt <= t; tt ++)
{
scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",
&L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);
scanf("%d%d",&n,&m);
for(i = 0; i < n; i ++)
scanf("%I64d",&p[i]);
/*初始化费用d[i][j]，也可以认为是距离和费用的转换 */
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
{
if(i == j) d[i][j] = 0; // 同一点木有距离
else {
temp = abs(p[i] - p[j]); //求两点距离
if(temp <= L1)
d[i][j] = C1;
else if(temp <= L2)
d[i][j] = C2;
else if(temp <= L3)
d[i][j] = C3;
else if(temp <= L4)
d[i][j] = C4;
else if(temp > L4)
d[i][j] = -1; //也可以定义成等于INF，当然INF需要足够大，至少大于100000000000
}
}
/* FLOYD算法 */
for(k = 0; k < n; k ++) //k相当于中转站！
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
if(d[i][k] != -1 && d[k][j] != -1) {
temp = d[i][k] + d[k][j];
if(temp < d[i][j] || d[i][j] == -1) //注意到d[i][j] == -1才是真正的大距离
d[i][j] = temp;
}
printf("Case %d:\n",tt);
for(i = 0; i < m; i ++)
{
scanf("%d%d",&a,&b);
if(d[a-1][b-1] == -1)
printf("Station %d and station %d are not attainable.\n",a,b);
else
printf("The minimum cost between station %d and station %d is %I64d.\n",a,b,d[a-1][b-1]);
}
}
return 0;
}
#include<stdio.h>
#include<math.h>
__int64 p[105],d[105][105];
int main()
{
int t,tt,n,m,a,b,i,j,k;
__int64 L1,L2,L3,L4,C1,C2,C3,C4,temp;
scanf("%d",&t); // 居然是少写了这句，所以t成了随机数，编译通过了
for(tt = 1; tt <= t; tt ++)
{
scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d",
&L1,&L2,&L3,&L4,&C1,&C2,&C3,&C4);
scanf("%d%d",&n,&m);
for(i = 0; i < n; i ++)
scanf("%I64d",&p[i]);
/*初始化费用d[i][j]，也可以认为是距离和费用的转换 */
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
{
if(i == j) d[i][j] = 0; // 同一点木有距离
else {
temp = abs(p[i] - p[j]); //求两点距离
if(temp <= L1)
d[i][j] = C1;
else if(temp <= L2)
d[i][j] = C2;
else if(temp <= L3)
d[i][j] = C3;
else if(temp <= L4)
d[i][j] = C4;
else if(temp > L4)
d[i][j] = -1; //也可以定义成等于INF，当然INF需要足够大，至少大于100000000000
}
}
/* FLOYD算法 */
for(k = 0; k < n; k ++) //k相当于中转站！
for(i = 0; i < n; i ++)
for(j = 0; j < n; j ++)
if(d[i][k] != -1 && d[k][j] != -1) {
temp = d[i][k] + d[k][j];
if(temp < d[i][j] || d[i][j] == -1) //注意到d[i][j] == -1才是真正的大距离
d[i][j] = temp;
}
printf("Case %d:\n",tt);
for(i = 0; i < m; i ++)
{
scanf("%d%d",&a,&b);
if(d[a-1][b-1] == -1)
printf("Station %d and station %d are not attainable.\n",a,b);
else
printf("The minimum cost between station %d and station %d is %I64d.\n",a,b,d[a-1][b-1]);
}
}
return 0;
}