- Car的旅行路线
- 2025-03-23 15:42:02 @
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int s,t,a,b,js=0;
double ans,dis12,dis13,dis23,maxn=-1;
double x[500],y[500],T[110],f[500][500];
double dis(int a,int b)
{
return sqrt((x[b]-x[a])*(x[b]-x[a])+(y[b]-y[a])*(y[b]-y[a]));
}
int main()
{
cin>>s>>t>>a>>b;
if(s==1)
{
cout<<"0.00";
return 0;
}
for(int i=1;i<=s;++i)
{
for(int j=1;j<=3;++j)
{
js++;
cin>>x[js]>>y[js];
}
cin>>T[i];
dis12=dis(js-2,js-1);
dis13=dis(js-2,js);
dis23=dis(js-1,js);
maxn=max(dis12,max(dis13,dis23));
if(maxn==dis12)
{
x[js+1]=x[js-2]+x[js-1]-x[js];
y[js+1]=y[js-2]+y[js-1]-y[js];
}
else if(maxn==dis13)
{
x[js+1]=x[js-2]+x[js]-x[js-1];
y[js+1]=y[js-2]+y[js]-y[js-1];
}
else if(maxn==dis23)
{
x[js+1]=x[js-1]+x[js]-x[js-2];
y[js+1]=y[js-1]+y[js]-y[js-2];
}
for(int k=1;k<=4;++k)
{
for(int j=1;j<=4;++j)
{
f[js+k-3][js+j-3]=dis(js+k-3,js+j-3)*T[i];
}
}
js++;
}
for(int i=1;i<=s;++i)
{
for(int j=i+1;j<=s;++j)
{
for(int o=1;o<=4;++o)
{
for(int p=1;p<=4;++p)
{
int k1=(i-1)*4+o;
int k2=(j-1)*4+p;
f[k1][k2]=f[k2][k1]=dis(k1,k2)*t;
}
}
}
}
for(int k=1;k<=s*4;++k)
{
for(int i=1;i<=s*4;++i)
{
for(int j=1;j<=s*4;++j)
{
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
ans=1000000;
for(int i=1;i<=4;++i)
{
for(int j=1;j<=4;++j)
{
int k1=(a-1)*4+i;
int k2=(b-1)*4+j;
ans=min(ans,f[k1][k2]);
}
}
printf("%0.2lf",ans);
return 0;
}