|
|
back to boardWhy i can't get AC,please help Posted by zhi 19 Mar 2002 17:39 here is my source.Thanks for everyone. #include<fstream.h> #include<math.h> #include<stdio.h> #define _MAX 2000000000 double v[2]; int n; int coun; double g[220][220]; double x[220]; double y[220]; double d[220]; int final[220]; int p[220]; double time(int i,int j,int how){ double temp; double x1=x[i]; double y1=y[i]; double x2=x[j]; double y2=y[j]; temp=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))/v[how]; return temp; } void init(){ cin>>v[0]>>v[1]; cin>>n; int i,j; for(i=0;i<n+2;i++) for(j=0;j<n+2;j++)g[i][j]=_MAX; for(i=0;i<n;i++) cin>>x[i]>>y[i]; int m,n1; while(1){ cin>>m>>n1; if(m==0||n1==0)break; g[m-1][n1-1]=time(m-1,n1-1,1); g[n1-1][m-1]=time(m-1,n1-1,1); } cin>>x[n]>>y[n]>>x[n+1]>>y[n+1]; //end input for(i=0;i<n+2;i++)g[n][i]=time(n,i,0); for(i=0;i<n;i++) for(j=0;j<n+2;j++) if(g[i][j]==_MAX)g[i][j]=time(i,j,0); //end init matrx for(i=0;i<n+2;i++){ d[i]=_MAX; p[i]=32767; final[i]=0; } d[n]=0; p[n]=n; final[n]=1; //end init; } void shestpath(){ int i,j,m,key; double min; key=n; for(i=0;i<n+2;i++){ min=_MAX; m=key; for(j=0;j<n+2;j++) if(d[key]+g[key][j]<d[j]){ d[j]=d[key]+g[key][j]; p[j]=key; } for(j=0;j<n+2;j++)if(d[j]<min&&final[j]==0){ min=d[j]; m=j; } key=m; final[m]=1; } } void process(int i){ if(p[i]==32767)return; if(i==n){ cout<<coun<<" "; return;} if(i<n&&i>=0)coun++; process(p[i]); if(i<n&&i>=0)cout<<(i+1)<<" "; } void print(){ if(d[n+1]!=_MAX){ printf("%.7lf",d[n+1]); cout<<endl; coun=0; process(n+1); } return; } void main(){ init(); shestpath(); print(); }
Publish your email,I'll send messages to you. Re: Publish your email,I'll send messages to you. Posted by zhi 21 Mar 2002 16:28 my e-mail is mench9@21cn.com,and can you tell me your e-mail? Thank you very much. |
|
|