http://acm.hdu.edu.cn/showproblem.php?pid=1690

才做了几天的DP专题，昨天的杭电全国邀请赛上居然就从头到尾都把它当DP做了

队里的3个人居然还会一致认为是DP，郁闷啊。。。。

其实只要floyed就可以过了的。。。。想复杂了啊。。。。。

#include<stdio.h>
#include<string.h>
__int64 l[5],c[5];
__int64 cost(__int64 len)
{
 if(len==0)
  return 0;
 else if(len<=l[1])
  return c[1];
 else if(len<=l[2])
  return c[2];
 else if(len<=l[3])
  return c[3];
 else if(len<=l[4])
  return c[4];
 else return -1;
}
int main()
{
 int test,i,j,n,m,t=0;
 __int64 k;
 __int64 distance[101][101],x[101],start[501],end[501];
 scanf("%d",&test);
 while(test--)
 {
  t++;
  scanf("%I64d%I64d%I64d%I64d",&l[1],&l[2],&l[3],&l[4]);
  scanf("%I64d%I64d%I64d%I64d",&c[1],&c[2],&c[3],&c[4]);
  scanf("%d%d",&n,&m);
  for(i=1;i<=n;i++)
   scanf("%I64d",&x[i]);
  for(i=1;i<=m;i++)
   scanf("%I64d%I64d",&start[i],&end[i]);
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    distance[i][j]=-1;
  for(i=1;i<=n;i++)
   for(j=i;j<=n;j++)
   {
    k=x[i]-x[j];
    if(k<0)
     k=-k;
    distance[i][j]=distance[j][i]=cost(k);
   }
  for(k=1;k<=n;k++)
   for(i=1;i<=n;i++)
    if(i!=j)
     for(j=1;j<=n;j++)
      if( j!=i && j!=k && distance[i][k]!=-1 && distance[k][j]!=-1 && (distance[i][k]+distance[k][j] < distance[i][j] || distance[i][j]==-1))
       distance[i][j]=distance[i][k]+distance[k][j];
  printf("Case %d:\n",t);
  for(i=1;i<=m;i++)
   if(distance[ start[i] ][ end[i] ]!=-1)
    printf("The minimum cost between station %I64d and station %I64d is %I64d.\n",start[i],end[i],distance[ start[i] ][ end[i] ]);
   else printf("Station %I64d and station %I64d are not attainable.\n",start[i],end[i]);
 }
 return 0;
}