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

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

Why i can't get AC,please help
Послано zhi 19 мар 2002 17:39
here is my source.Thanks for everyone.
#include<fstream.h>
#include<math.h>
#include<stdio.h>
#define _MAX 2000000000
double v[2];
int n;
int coun;
double g[220][220];
double x[220];
double y[220];
double d[220];
int final[220];
int p[220];

double time(int i,int j,int how){
      double temp;
      double x1=x[i];
      double y1=y[i];
      double x2=x[j];
      double y2=y[j];
     temp=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))/v[how];
      return temp;
}
void init(){
    cin>>v[0]>>v[1];
    cin>>n;
    int i,j;
    for(i=0;i<n+2;i++)
        for(j=0;j<n+2;j++)g[i][j]=_MAX;
        for(i=0;i<n;i++)
             cin>>x[i]>>y[i];
      int m,n1;
      while(1){
      cin>>m>>n1;
      if(m==0||n1==0)break;
        g[m-1][n1-1]=time(m-1,n1-1,1);
        g[n1-1][m-1]=time(m-1,n1-1,1);
      }
      cin>>x[n]>>y[n]>>x[n+1]>>y[n+1];
      //end input
      for(i=0;i<n+2;i++)g[n][i]=time(n,i,0);
      for(i=0;i<n;i++)
          for(j=0;j<n+2;j++)
              if(g[i][j]==_MAX)g[i][j]=time(i,j,0);
//end init matrx
              for(i=0;i<n+2;i++){
                  d[i]=_MAX;
                  p[i]=32767;
                  final[i]=0;
              }
              d[n]=0;
              p[n]=n;
              final[n]=1;
            //end init;
}

void shestpath(){
    int i,j,m,key;
    double min;
    key=n;
    for(i=0;i<n+2;i++){
         min=_MAX;
         m=key;
         for(j=0;j<n+2;j++)
             if(d[key]+g[key][j]<d[j]){
                 d[j]=d[key]+g[key][j];
                 p[j]=key;
             }
             for(j=0;j<n+2;j++)if(d[j]<min&&final[j]==0){
                 min=d[j];
                 m=j;
             }
             key=m;
             final[m]=1;
             }
}
void process(int i){
     if(p[i]==32767)return;
     if(i==n){
         cout<<coun<<" ";
         return;}
     if(i<n&&i>=0)coun++;
     process(p[i]);
     if(i<n&&i>=0)cout<<(i+1)<<" ";
}
void print(){
    if(d[n+1]!=_MAX){
          printf("%.7lf",d[n+1]);
         cout<<endl;
          coun=0;
         process(n+1);
    }
    return;
}
void main(){
    init();
    shestpath();
    print();
}
Publish your email,I'll send messages to you.
Послано Blue cat 20 мар 2002 12:18
Re: Publish your email,I'll send messages to you.
Послано zhi 21 мар 2002 16:28
my e-mail is mench9@21cn.com,and can you tell me your e-mail?
Thank you very much.