ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1207. Медиана на плоскости

Показать все сообщения Спрятать все сообщения

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'? Meo Meo 7 апр 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'? Fair Rosmarin 7 апр 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 Oleg 6 ноя 2002 19:32