1 条题解

  • 1

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

  • 1

信息

ID
1362
难度
9
分类
图结构 | 最短路 点击显示
标签
递交数
4
已通过
4
通过率
100%
上传者