|
|
back to boardHow to do '1205'? Posted by ting 7 Apr 2002 14:43 Please tell me how to do '1205'. Thank you very much. Re: How to do '1205'? > Please tell me how to do '1205'. > Thank you very much. > There is N + 2 points, n station and A, B. You find the minimum way from A to B. Between 2 point, if they are two station then go by train else go on foot. I hope you will complete it soon. Re: How to do '1205'? > Please tell me how to do '1205'. > Thank you very much. > The code is as follows: #include <iostream.h> #include <memory.h> #include <iomanip.h> #include <math.h> struct point { double x,y; }; point p[201]; int N; double fv,cv; double graph[202][202]; double dist[202]; int pre[202]; bool s[202]; void main() { cin>>fv>>cv; cin>>N; int i; for (i=1;i<=N;i++) cin>>p[i].x>>p[i].y; int a,b; cin>>a>>b; memset(graph,-1,sizeof(graph)); while ( a>0 && b>0 ) { graph[a][b] = 1; graph[b][a] = 1; cin>>a>>b; } cin>>p[0].x>>p[0].y; cin>>p[N+1].x>>p[N+1].y; int j; for (i=0;i<=N+1;i++) for (j=0;j<=N+1;j++) { if ( i==j ) continue; if ( graph[i][j]==0 ) graph[i][j] = sqrt((p[i].x-p[j].x)*(p [i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/fv; else graph[i][j] = sqrt((p[i].x-p[j].x)*(p[i].x- p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/cv; } pre[0] = -1; for (i=1;i<=N+1;i++) { dist[i] = graph[i][0]; pre[i] = 0; s[i] = false; } s[0] = true; dist[0] = 0; for (i=0;i<N+1;i++) { double min = 999999; int u = 0; for (j=0;j<=N+1;j++) if ( !s[j] && min>dist[j] ) { u = j; min = dist[j]; } s[u] = true; if ( s[N+1] ) break; for (j=0;j<=N+1;j++) if ( !s[j] && dist[u]+graph[u][j]<dist [j] ) { dist[j] = dist[u]+graph[u][j]; pre[j] = u; } } cout<<setiosflags(ios::fixed)<<setprecision(7)<<dist[N+1] <<endl; int t[202]; int n=0,k = N+1; while ( pre[k]>0 ) { t[n++] = pre[k]; k = pre[k]; } if ( n==0 ) cout<<0<<endl; else { cout<<n<<' '<<t[n-1]; for (i=n-2;i>=0;i--) cout<<' '<<t[i]; cout<<endl; } }
IT is wrong TL Posted by Oleg 6 Nov 2002 19:32 |
|
|