- 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;
}