| 
 | 
вернуться в форумHow to do '1205'? Послано  ting 7 апр 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 Послано  Oleg 6 ноя 2002 19:32  |  
  | 
|