Why WA? Help anyone?
Posted by
asif 26 Mar 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;
}