首页 > 代码库 > Bus System(Flody)
Bus System(Flody)
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。