首页 > 代码库 > Bus System（Flody)

Bus System（Flody)

2024-07-10 00:38:28   228人阅读

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

坑爹的题，必须用__int64 %I64d(以前没用过）

因为这题的数据特别大，所以用-1

  1 #include <iostream>  2 #include <stdio.h>  3 #include <string.h>  4 #include <stdlib.h>  5 #include <math.h>  6 using namespace std;  7 __int64 map[102][102];  8 __int64 L[5],C[5];  9 __int64 a[102]; 10 int n,m; 11 void Floy() 12 { 13     for(int k=1;k<=n;k++) 14     { 15         for(int i=1;i<=n;i++) 16         { 17             for(int j=1;j<=n;j++) 18             { 19                 if(map[i][k]==-1||map[k][j]==-1)// 20                     continue; 21                 if(map[i][j]==-1||map[i][k]+map[k][j]<map[i][j])//执行这步，说明map[i][k],map[k][j]都存在 22                     map[i][j]=map[i][k]+map[k][j]; 23             } 24         } 25     } 26 } 27  28 int main() 29 { 30     int T; 31     int K=0; 32     scanf("%d",&T); 33     while(T--) 34     { 35         K++; 36         for(int i=1;i<=4;i++) 37             scanf("%I64d",&L[i]); 38         for(int i=1;i<=4;i++) 39             scanf("%I64d",&C[i]); 40             scanf("%d%d",&n,&m); 41         for(int i=1;i<=n;i++) 42         { 43             scanf("%I64d",&a[i]); 44         } 45         __int64 t; 46         for(int i=1;i<=n;i++) 47         { 48             for(int j=1;j<=n;j++) 49             { 50  51                t=abs(a[j]-a[i]);//这里自己出错了，输入时坐标是不会按顺序输入的 52  53                if(t==0) 54                { 55                    map[i][j]=0; 56                    map[j][i]=0; 57                } 58                else if(t>0&&t<=L[1]) 59                { 60                     map[i][j]=C[1]; 61                     map[j][i]=C[1]; 62  63                } 64                else if(t>L[1]&&t<=L[2]) 65                { 66                        map[i][j]=C[2]; 67                        map[j][i]=C[2]; 68  69                } 70                 else if(t>L[2]&&t<=L[3]) 71                { 72  73  74                        map[i][j]=C[3]; 75                        map[j][i]=C[3]; 76  77                } 78                 else if(t>L[3]&&t<=L[4]) 79                { 80  81  82                        map[i][j]=C[4]; 83                        map[j][i]=C[4]; 84  85                } 86                else 87                { 88                    map[i][j]=-1; 89                    map[j][i]=-1; 90                } 91  92             } 93         } 94         Floy(); 95          printf("Case %d:\n",K); 96         int yy,uu; 97         for(int i=0;i<m;i++) 98         { 99             scanf("%d%d",&yy,&uu);100             if(map[yy][uu]==-1)101                 printf("Station %d and station %d are not attainable.\n",yy,uu);102             else103             {104                 printf("The minimum cost between station %d and station %d is %I64d.\n",yy,uu,map[yy][uu]);105 106             }107         }108 109     }110     return 0;111 }

 


联系
我们