ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1207. Median on the Plane

How 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'?
Posted by Meo Meo 7 Apr 2002 15:44
> 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'?
Posted by Fair Rosmarin 7 Apr 2002 22:31
> 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