题解：AT_abc374_d [ABC374D] Laser Marking

zeroflows · 2024-10-06 09:53:25 · 题解

题目传送门

思路

注意一下数据范围。

• 1 \le n \le 6

首先想到 dfs。

按照题意，先算出位置到线段的一段所需的时间。\ 再算出画线段所需的时间，就行了。\ 输出后发现与答案不一样，没关系，只要小数后六位是对的就行了。\ 记得要分情况，看先移动的线段的那一头。

代码

#include<bits/stdc++.h>
using namespace zh;
double ans=double(LLONG_MAX);
bool v[100];
int a[10000],b[10000],c[10000],d[10000];
int n,s,t;
void dfs(int x,int y,int z,double ss)
{
    if(z==n)
    {
        ans=min(ans,ss);
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!v[i])
        {
            v[i]=1;
            double q1=sqrt(double(a[i]-x)*double(a[i]-x)+double(b[i]-y)*double(b[i]-y));
            double q2=sqrt(double(a[i]-c[i])*double(a[i]-c[i])+double(b[i]-d[i])*double(b[i]-d[i]));
            dfs(c[i],d[i],z+1,ss+q1/s+q2/t);
            q1=sqrt(double(c[i]-x)*double(c[i]-x)+double(d[i]-y)*double(d[i]-y));
            dfs(a[i],b[i],z+1,ss+q1/s+q2/t);
            v[i]=0;
        }
    }
}
int main(){
    //  ios::sync_with_stdio(false);
    //  cin.tie(),cout.tie();
    //  freopen(".in","r",stdin);
    //  freopen(".out","w",stdout);
    cin>>n>>s>>t;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    dfs(0,0,0,0);
    printf("%.20lf",ans);
}