题意：此题唯一亢爹的就是，输入的站号可能是负数，但是起点到终点的站号不可能是负数，下面举个例你就清楚了，
如输入站号顺序为：-1 ，-2， -3， -4， 1， 2， 3， 4.
若L1-L4，C1-C4分别为1 2 3 4 1 3 5 7，问1到5的最短路径，
答案：3.很多我想你会认为不能到达，但最短路径确是3.
原因是：-1(代号为1)，-2(代号为2)， -3(代号为3)， -4(代号为4)， 1(代号为5)， 2(代号为6)， 3(代号为7)， 4(代号为8)
问：1到5的最短路径其实是问-1到1的最短路径。2到5的最短路径其实是问-2到1的最短路径。8到5的最短路径其实是问4到1的最短路径。
解法：floyd
ac代码：
View Code
#include<iostream> //#include<cmath> //#include <cstdio> using namespace std; const __int64 INT=0x7ffffffffff; const int M=100+99; __int64 a[4]; __int64 b[4]; __int64 stat[110],last[590][2]; __int64 n,m; __int64 map[M][M]; void floyd() { int i,j,k; for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) { if(map[i][k]+map[k][j]<map[i][j]) { map[i][j]=map[i][k]+map[k][j]; } } } __int64 abs(__int64 x) { if(x<0) return -x; else return x; } int main() { /*freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); */ __int64 k=1; __int64 t ; cin>>t; while(t--) { memset(stat,0,sizeof(stat)); memset(last,0,sizeof(last)); memset(map,0,sizeof(map)); __int64 i,j; for(i=0;i<4;i++) scanf("%I64d",&a[i]); for(i=0;i<4;i++) scanf("%I64d",&b[i]); cin>>n>>m; for(i=0;i<n;i++) scanf("%I64d",&stat[i]); for(i=0;i<m;i++) scanf("%I64d%I64d",&last[i][0],&last[i][1]); __int64 len; for(i=0;i<n;i++) { for(j=0;j<n;j++) { len=abs(stat[i]-stat[j]); if(len==0) map[i][j]=0; else if(len<=a[0]) map[i][j]=b[0]; if(len>a[0]&&len<=a[1]) map[i][j]=b[1]; if(len>a[1]&&len<=a[2]) map[i][j]=b[2]; if(len>a[2]&&len<=a[3]) map[i][j]=b[3]; if(len>a[3]) map[i][j]=INT; } } __int64 lenl; printf("Case %d:\n",k++); floyd(); for(i=0;i<m;i++) { if(map[last[i][0]-1][last[i][1]-1]<INT) printf("The minimum cost between station %I64d and station %I64d is %I64d.\n", last[i][0],last[i][1],map[last[i][0]-1][last[i][1]-1]); else printf("Station %I64d and station %I64d are not attainable.\n",last[i][0],last[i][1]); } } return 0; } /* 1 2 3 4 1 3 5 7 8 5 1 2 3 4 -1 -2 -3 -4 1 4 4 1 1 2 4 2 7 6 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 8 3 1 2 3 4 -1 -2 -3 -4 1 4 4 6 7 6 1 2 3 4 1 3 5 7 4 1 1 2 3 10 1 4 */