|  | 
|  | 
| back to board | How to do '1205'? Posted by ting  7 Apr 2002 14:43Please 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 | 
 | 
|