一个人的旅行 HDU 2066 &&HDU Today HDU 2112
一个人的旅行 HDU 2066
迪杰斯特拉：Dijkstra：
1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<string.h> 5 using namespace std; 6 int inf=1000000;//以后如果结果输出的是（负数或很大的整数），可能是（这个开大了或开小了） 7 int a[1005][1005],w[1005]; 8 int main() 9 { 10 int t,s,d,n,i,j,p,min1,a1,a2,a3; 11 while(scanf("%d%d%d",&t,&s,&d)!=EOF) 12 { 13 memset(a,inf,sizeof(a)); 14 n=0; 15 while(t--) 16 { 17 scanf("%d%d%d",&a1,&a2,&a3); 18 if(a[a1][a2]>a3) 19 { 20 a[a1][a2]=a3; 21 a[a2][a1]=a3; 22 } 23 if(a1>n) n=a1; 24 if(a2>n) n=a2; 25 } 26 n++; 27 for(i=1;i<=n;i++) 28 a[i][i]=0; 29 while(s--) 30 { 31 scanf("%d",&a1); 32 a[0][a1]=0; 33 } 34 while(d--) 35 { 36 scanf("%d",&a1); 37 a[a1][n]=0; 38 } 39 memset(w,0,sizeof(w)); 40 for(i=1;i<=n;i++) 41 { 42 min1=inf; 43 for(j=1;j<=n;j++) 44 if(!w[j]&&min1>a[0][j]) 45 { 46 p=j; 47 min1=a[0][j]; 48 } 49 w[p]=1; 50 for(j=1;j<=n;j++) 51 if(!w[j]&&a[0][j]>a[0][p]+a[p][j]) 52 { 53 a[0][j]=a[0][p]+a[p][j]; 54 a[j][0]=a[0][j]; 55 } 56 } 57 printf("%d ",a[0][n]); 58 } 59 return 0; 60 }
下面讲一下这个迪杰斯特拉算法的意思：
就是以起点开始，先找到一个中间点（相比之下最小的那个），再以这个中间点作为桥梁，更新起点通过中间点到其他点的距离。以后反复循环，以前做过中间点的，就可以跳过此步骤，当里面的点全部都做过中间点或没有被赋值的（初始值为很大的一个数），就可以跳过此循环了。
这个算法的复杂度应该是n^2，比弗洛伊德算法（Floyd算法）n^3快一些！！！！
注意：（求最小径的二维数组）（每次赋值要进行俩次，因为他们是对称的！！）（还有起点与终点在同一位置的情况）
下面的这个题目要用map来转换字符串！！（第一次见到用map）思考！！！！！！！！！
HDU Today HDU 2112
就是难点在map：
可以用Floyd或Dijkstra：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<map> 5 #include<string.h> 6 #include<string> 7 using namespace std; 8 int a[155][155]; 9 char a3[35],b[35],a1[35],a2[35]; 10 map<string,int> q; 11 int main() 12 { 13 int n,i,j,m,d,k; 14 while(scanf("%d",&n)!=EOF) 15 { 16 if(n==-1) 17 break; 18 if(n==0) 19 { 20 printf("-1 "); 21 continue; 22 } 23 q.clear(); 24 memset(a,10000,sizeof(a)); 25 scanf("%s%s",a3,b); 26 q[a3]=1;//因为起点和终点可以一样的！ 27 q[b]=2;//同上 28 m=2; 29 while(n--) 30 { 31 scanf("%s%s%d",a1,a2,&d); 32 if(!q[a1]) 33 q[a1]=++m; 34 if(!q[a2]) 35 q[a2]=++m; 36 if(a[q[a1]][q[a2]]>d) 37 { 38 a[q[a1]][q[a2]]=d; 39 a[q[a2]][q[a1]]=d; 40 } 41 } 42 for(i=1;i<=m;i++) 43 a[i][i]=0; 44 for(k=1;k<=m;k++) 45 for(i=1;i<=m;i++) 46 for(j=i+1;j<=m;j++) 47 { 48 if(a[i][j]>a[i][k]+a[k][j]) 49 { 50 a[i][j]=a[i][k]+a[k][j]; 51 a[j][i]=a[i][j]; 52 } 53 } 54 if(a[q[a3]][q[b]]<10000) 55 printf("%d ",a[q[a3]][q[b]]);56 else 57 printf("-1 "); 58 } 59 return 0; 60 }
那么接下用Dijkstra意义也不大：
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<map> 5 #include<string.h> 6 #include<string> 7 using namespace std; 8 int a[155][155],w[155]; 9 char a3[35],b[35],a1[35],a2[35]; 10 map<string,int> q; 11 int main() 12 { 13 int n,i,j,m,d,p,min1; 14 while(scanf("%d",&n)!=EOF) 15 { 16 if(n==-1) 17 break; 18 if(n==0) 19 { 20 printf("-1 "); 21 continue; 22 } 23 q.clear(); 24 memset(a,10000,sizeof(a)); 25 scanf("%s%s",a3,b); 26 q[a3]=1; 27 q[b]=2; 28 m=2; 29 while(n--) 30 { 31 scanf("%s%s%d",a1,a2,&d); 32 if(!q[a1]) 33 q[a1]=++m; 34 if(!q[a2]) 35 q[a2]=++m; 36 if(a[q[a1]][q[a2]]>d) 37 { 38 a[q[a1]][q[a2]]=d; 39 a[q[a2]][q[a1]]=d; 40 } 41 } 42 for(i=1;i<=m;i++) 43 a[i][i]=0; 44 memset(w,0,sizeof(w)); 45 for(i=1;i<=m;i++) 46 { 47 min1=10000; 48 for(j=1;j<=m;j++) 49 if(!w[j]&&min1>a[1][j]) 50 { 51 p=j; 52 min1=a[1][j]; 53 } 54 w[p]=1; 55 for(j=1;j<=m;j++) 56 if(!w[j]&&a[1][j]>a[1][p]+a[p][j]) 57 { 58 a[1][j]=a[1][p]+a[p][j]; 59 a[j][1]=a[1][j]; 60 } 61 } 62 if(a[q[a3]][q[b]]<10000) 63 printf("%d ",a[q[a3]][q[b]]); 64 else 65 printf("-1 "); 66 } 67 return 0; 68 }
for(i=0,h=0;i<m;i++)
{
c[i]=a1[i]+b1[i]+h;
h=c[i]/10;
c[i]=c[i]%10;
}
for(i=0;i<m;i++)
{
h=a1[i]+b1[i];
c[i]=c[i]+h%10;//这个地方可能为10啊！！！！！！！！！！！！！！！！！！（严谨啊大哥。。。）
c[i+1]=c[i+1]+h/10;
}