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 1205. By the Underground or by Foot?

Why i can't get AC,please help
Posted by zhi 19 Mar 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.
Posted by Blue cat 20 Mar 2002 12:18
Re: Publish your email,I'll send messages to you.
Posted by zhi 21 Mar 2002 16:28
my e-mail is mench9@21cn.com,and can you tell me your e-mail?
Thank you very much.