题意：此题唯一亢爹的就是，输入的站号可能是负数，但是起点到终点的站号不可能是负数，下面举个例你就清楚了，如输入站号顺序为：-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的最短路径。
解法：dijkstar
ac代码：
View Code
#include<iostream> using namespace std; const __int64 INT=0x7ffffffffff;//INT作为无限大，此题必须很大 const int M=100+99; __int64 a[4];//存储L1 L2 L3 L4 __int64 b[4];//存储C1 C2 C3 C4 __int64 stat[110],last[590][2];//stat[]存站,last[][]存起点和终点 bool use[M]; //dijkstar用作标记 __int64 n,m; __int64 map[M][M];//存站与站之间的花费， __int64 dis[M]; //最短路径 __int64 disk(__int64 start,__int64 end,__int64 n)//dijkstar（最短路径算法） { memset(use,0,sizeof(use)); __int64 i,j; for(i=0;i<n;i++) dis[i]=INT; __int64 min,mid; __int64 foat; dis[start]=0; for(i=0;i<n;i++) { min=INT; foat=0; //若找不到dis[i]最小值则跳出循环 for(j=0;j<n;j++) { if(!use[j]&&min>dis[j]) { min=dis[j]; mid=j; foat=1; } } if(foat==0) break; else use[mid]=1; for(j=0;j<n;j++) { if(!use[j]&&dis[j]>dis[mid]+map[mid][j])//松弛战术 dis[j]=dis[mid]+map[mid][j]; } } return dis[end]; } __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++); for(i=0;i<m;i++) { lenl=disk(last[i][0]-1,last[i][1]-1,n);//因为map[][]的下标示从0开始的，所以必须是last[][]-1,才能代表站的代号 if(lenl<INT) printf("The minimum cost between station %I64d and station %I64d is %I64d.\n",last[i][0],last[i][1],lenl); 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 5 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 */