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

Обсуждение задачи 1205. На метро или пешком?

Why WA? Help anyone?
Послано asif 26 мар 2002 10:53
# include <stdio.h>
# include <math.h>

# define MAX 200
# define hypot(a,b) sqrt((a)*(a)+(b)*(b))

double vw,vu,x[MAX],y[MAX],t[MAX][MAX];
int n,p[MAX][MAX];
double ax,ay,bx,by;

int main(void)
{
  double mintime,time;
  int mini,minj;
  int stack[MAX],top;
  int i,j,k;
  scanf("%lf%lf",&vw,&vu);
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%lf%lf",&x[i],&y[i]);
  for(i=0;i<n;i++){
    t[i][i]=0;
    p[i][i]=i;
  }
  for(i=0;i<n;i++)
    for(j=i+1;j<n;j++){
      t[i][j]=t[j][i]=hypot(x[i]-x[j],y[i]-y[j])/vw;
      p[i][j]=i;
      p[j][i]=j;
    }
  while(scanf("%d%d",&i,&j)==2 && i && j){
    i--;
    j--;
    t[i][j]=t[j][i]=hypot(x[i]-x[j],y[i]-y[j])/vu;
  }
  scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);
  for(k=0;k<n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
    if(t[i][j]>t[i][k]+t[k][j]){
      t[i][j]=t[i][k]+t[k][j];
      p[i][j]=p[k][j];
    }
  mintime=1e30;
  for(i=0;i<n;i++)
   for(j=0;j<n;j++){
    time=hypot(ax-x[i],ay-y[i])/vw+t[i][j]+hypot(x[j]-bx,y[j]-by)/vw;
      if(time<mintime){
    mintime=time;
    mini=i;
    minj=j;
      }
    }
  printf("%.7lf\n",mintime);
  i=mini;
  j=minj;
  top=0;
  while(i!=j){
    k=p[i][j];
    stack[top++]=j+1;
    j=k;
  }
  stack[top++]=i+1;
  printf("%d",top);
  while(top--)
    printf(" %d",stack[top]);
  printf("\n");
  return 0;
}