|
|
back to boardWho can help me!why wrong??? Posted by t c 20 Apr 2002 22:53 #include<fstream.h> #include<stdio.h> #include<math.h> struct data { int adjvex; double lowcost; int in_g; }closedge[210]; int n; double distance[210][210]; double g_speed,r_speed; double sx_dt[210],sy_dt[210],ax_d,ay_d,bx_d,by_d; /////////////////////////// void read() { int i,j; double tempx,tempy; cin>>r_speed>>g_speed; cin>>n; for(i=1;i<=n;i++) cin>>sx_dt[i]>>sy_dt[i]; for(i=0;i<=n+1;i++) for(j=0;j<=n+1;j++) distance[i][j]=-1; cin>>i>>j; while(i!=0||j!=0) { tempx=sx_dt[i]-sx_dt[j]; tempy=sy_dt[i]-sy_dt[j]; distance[j][i]=distance[i][j]=sqrt (tempx*tempx+tempy*tempy)/g_speed; cin>>i>>j; } cin>>ax_d>>ay_d>>bx_d>>by_d; for(i=1;i<=n;i++) { tempx=sx_dt[i]-ax_d; tempy=sy_dt[i]-ay_d; distance[i][0]=distance[0][i]=sqrt (tempx*tempx+tempy*tempy)/r_speed; tempx=sx_dt[i]-bx_d; tempy=sy_dt[i]-by_d; distance[i][n+1]=distance[n+1][i]=sqrt (tempx*tempx+tempy*tempy)/r_speed; } tempx=ax_d-bx_d;tempy=ay_d-by_d; distance[n+1][0]=distance[0][n+1]=sqrt (tempx*tempx+tempy*tempy)/r_speed; } ////////////////// int find_min() { int i,mini=1; double min=-1; for(i=1;i<=n+1;i++) { if(closedge[i].in_g==0) if(min==-1||min>closedge[i].lowcost) { mini=i; min=closedge[i].lowcost; } } return mini; } //////////////////////////// void main() { int i,j,k; int route[210],rou_num=0; double tempx,tempy; //freopen("in.txt","r",stdin); read();//return; k=0;closedge[0].adjvex=0;closedge[0].in_g=1;closedge[0].lowcost=0;
for(i=1;i<=n+1;i++){closedge[i].adjvex=0;closedge [i].lowcost=distance[0][i];closedge[i].in_g=0;}
for(i=1;i<=n+1;i++) { k=find_min(); //cout<<k<<" ";//return ; if(k==(n+1))break; closedge[k].in_g=1; for(j=1;j<=n+1;j++) if(closedge[j].in_g==0) if(distance[k][j]>=0&&distance[k][j]+closedge [k].lowcost<closedge[j].lowcost) { closedge[j].adjvex=k;closedge [j].lowcost=distance[k][j]+closedge[k].lowcost; } } cout.precision(8); cout<<closedge[n+1].lowcost<<endl; k=n+1; //cout<<closedge[n+1].adjvex;return ; while(k!=0) { rou_num++; k=route[rou_num]=closedge[k].adjvex; } cout<<(rou_num-1);//return ; for(i=rou_num-1;i>=1;i--) cout<<" "<<route[i]; } |
|
|