Bus System

杭电1690
不理解
View Code
 1 #include<stdio.h>
 2 #include<iostream>
 3 using namespace std;
 4 #define maxint 0x7f7f7f7f7f7f7f7fLL
 5 typedef __int64 LL;
 6 LL mat[105][105];
 7 LL cor[105];
 8 LL l1,l2,l3,l4,c1,c2,c3,c4;
 9 int n;
10 LL change(LL x)
11 {
12     if(x<0) x=-x;
13     if(x>0&&x<=l1) return c1;
14     if(x>l1&&x<=l2) return c2;
15     if(x>l2&&x<=l3) return c3;
16     if(x>l3&&x<=l4) return c4;
17     if(x>l4) return maxint;
18 }
19 
20 void floyd()
21 {
22     int i,j,k;
23     for(k=1;k<=n;k++)
24         for(i=1;i<=n;i++)
25             for(j=1;j<=n;j++)
26                 if(mat[i][k]!=maxint&&mat[k][j]!=maxint)
27                     if(mat[i][j]>mat[i][k]+mat[k][j])
28                         mat[i][j]=mat[i][k]+mat[k][j];
29 }
30 int main()
31 {
32     int t,i,j,m,cas=1;
33     scanf("%d",&t);
34     while(t--)
35     {
36         printf("Case %d:\n",cas++);
37         scanf("%I64d %I64d %I64d %I64d %I64d %I64d %I64d %I64d",&l1,&l2,&l3,&l4,&c1,&c2,&c3,&c4);
38         scanf("%d%d",&n,&m);
39         for(i=1;i<=n;i++)
40             scanf("%I64d",&cor[i]);
41         for(i=1;i<=n;i++)
42             for(j=i+1;j<=n;j++)
43             {
44                 LL x=cor[i]-cor[j];
45                 mat[i][j]=mat[j][i]=change(x);
46             }
47      floyd();
48      while(m--)
49      {
50          int x,y;
51          scanf("%d%d",&x,&y);
52          if(mat[x][y]!=maxint)
53              printf("The minimum cost between station %d and station %d is %I64d.\n",x,y,mat[x][y]);
54           else
55               printf("Station %d and station %d are not attainable.\n",x,y);
56      }
57     }
58     return 0;
59 }