看不懂D哪错了
查看原帖
看不懂D哪错了
941575
Stars_visitor_tyw楼主2024/10/5 22:06
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define double long double
struct node
{
    int xx,yy,xxx,yyy;
    double length()const
	{
        return sqrt((xxx-xx)*(xxx-xx)+(yyy-yy)*(yyy-yy));
    }
};
double disd(int xx,int yy,int xxx,int yyy)
{
    return sqrt((xxx-xx)*(xxx-xx)+(yyy-yy)*(yyy-yy));
}
double ptime(const node&a,double b)
{
    return a.length()/b;
}
double moved(int curx,int cury,const node&a,double s)
{
    return disd(curx,cury,a.xx,a.yy)/s;
}
bool vis[100];
void dfs(int cur,const node a[],double s,double t,int curx,int cury,double& mini,double curt,int n)
{
    if(cur==n)
	{
        mini=min(mini,curt);
        return;
    }
    for(int i=0;i<n;i++)
	{
        if(!vis[i])
		{
            vis[i]=1;
            double mt=moved(curx,cury,a[i],s);
            double pt=ptime(a[i],t);
            dfs(cur+1,a,s,t,a[i].xxx,a[i].yyy,mini,mt+pt+curt,n);
            dfs(cur+1,a,s,t,a[i].xx,a[i].yy,mini,mt+pt+curt,n);
            vis[i]=0;
        }
    }
}
signed main()
{
    int n;
    double s,t;
    cin>>n>>s>>t;
    node a[100];
    for(int i=0;i<n;i++)
	{
        cin>>a[i].xx>>a[i].yy>>a[i].xxx>>a[i].yyy;
    }
    double mini=numeric_limits<double>::max();
    dfs(0,a,s,t,0,0,mini,0,n);
    cout<<fixed<<setprecision(16)<<mini<<endl;
    return 0;
}

跟答案差不太远,但https://atcoder.jp/contests/abc374/submissions/58485048

2024/10/5 22:06
加载中...