ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1205. By the Underground or by Foot?

I thick this is the correct method!
Posted by crazy 12 May 2002 12:52

#include<iostream.h>
#include<math.h>
#include<stdio.h>

double x[201],y[201];
double time[201][201];
int   path[201][201];
int p[201];

void main()
{
double Byfoot,Bybus,t;
double xa,ya,xb,yb;
double ans;
double temp;

int begin,end;
int i,j,k;
int tempi,tempj;
int N;
int tot;

cin>>Byfoot>>Bybus;
cin>>N;
for(i=1;i<=N;i++){
cin>>x[i]>>y[i];
}

for(i=1;i<=N;i++)
for(j=i+1;j<=N;j++){
t=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y
[j]))/Byfoot;
time[i][j]=t;
time[j][i]=t;
path[i][j]=j;
path[j][i]=i;
}

while(1){
cin>>begin>>end;
if(!begin||!end) break;
t=sqrt((x[begin]-x[end])*(x[begin]-x[end])+(y[begin]-y[end])*(y
[begin]-y[end]))/Bybus;
time[begin][end]=t;
time[end][begin]=t;
path[begin][end]=end;
path[end][begin]=begin;
}
for(k=1;k<=N;k++)      //using flode here
for(i=1;i<=N;i++)
for(j=1;j<=N;j++){
if(time[i][k]+time[k][j]<time[i][j]){
time[i][j]=time[i][k]+time[k]
[j];
path[i][j]=path[i][k];
}
}
cin>>xa>>ya>>xb>>yb;
ans=sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb))/Byfoot;
tempi=0;
tempj=0;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++){
if(path[i][j]==0) continue;
temp=sqrt((xa-x[i])*(xa-x[i])+(ya-y[i])*(ya-y
[i]))/Byfoot;
temp+=sqrt((xb-x[j])*(xb-x[j])+(yb-y[j])*(yb-y
[j]))/Byfoot;
temp+=time[i][j];
if(temp<ans){
ans=temp;
tempi=i;
tempj=j;
}
}
printf("%.7f\n",ans);
if(tempi==0&&tempj==0) cout<<0<<endl;
else{
tot=0;
p[tot++]=tempi;
while(tempi!=tempj){
tempi=path[tempi][tempj];
p[tot++]=tempi;
}
cout<<tot;
for(i=0;i<tot;i++){
cout<<" "<<p[i];
}
cout<<endl;
}
}
But...
Posted by crazy 12 May 2002 12:53