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

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

Help! Why my program got WA?
Послано Savior 13 май 2002 22:37
#include<fstream.h>
#include<math.h>
#define maxn 201

struct Tpoint {double x,y;};

int n,p0,p1,wt;
double v1,v2,mint;
Tpoint p[maxn],a,b;
double w[maxn][maxn];
unsigned char path[maxn][maxn],way[maxn];

double dis(Tpoint g,Tpoint h)
{
  return sqrt((g.x-h.x)*(g.x-h.x)+(g.y-h.y)*(g.y-h.y));
}

void init()
{
  int i,j;

  cin>>v1>>v2>>n;
  for(i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
  for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
      {
    w[i][j]=dis(p[i],p[j])/v1;
    w[j][i]=w[i][j];
    path[i][j]=0;path[j][i]=0;
      }
  do
    {
      cin>>i>>j;
      if(i>0)
    {
      w[i][j]=dis(p[i],p[j])/v2;
      w[j][i]=w[i][j];
    }
    } while(i>0);
  cin>>a.x>>a.y;
  cin>>b.x>>b.y;
}

void pr(int g,int h)
{
  if(path[g][h]==0) return;
  pr(g,way[wt]);
  wt++;way[wt]=path[g][h];
  pr(way[wt],h);
}

void print()
{
  int i;

  cout.setf(ios::fixed);
  cout.setf(ios::showpoint);
  cout.precision(7);
  cout<<mint<<endl;
  wt=0;
  if(p0>0)
    {
      wt=1;way[1]=p0;
      pr(p0,p1);
      wt++;way[wt]=p1;
    }
  cout<<wt;
  for(i=1;i<=wt;i++) cout<<" "<<int(way[i]);
  cout<<endl;
}

void scan()
{
  int i,j,k;
  double u,to[maxn][2];

  for(k=1;k<=n;k++)
    for(i=1;i<n;i++) if(i!=k)
      for(j=i+1;j<=n;j++) if(j!=k)
    {
      u=w[i][k]+w[j][k];
      if(u<w[i][j])
        {
          w[i][j]=u;w[j][i]=u;
          path[i][j]=k;path[j][i]=k;
        }
    }
  for(i=1;i<=n;i++)
    {
      to[i][0]=dis(a,p[i])/v1;
      to[i][1]=dis(b,p[i])/v1;
    }
  mint=dis(a,b)/v1;
  p0=0;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++) if(i!=j)
      {
    u=to[i][0]+to[j][1]+w[i][j];
    if(u<mint)
      {
        mint=u;
        p0=i;p1=j;
      }
      }
}

void main()
{
  init();
  scan();
  print();
}