wa*6求调
查看原帖
wa*6求调
1001837
xiali081913楼主2024/10/13 09:59
#include <bits/stdc++.h>
using namespace std;
long long n,s,t,x[100],y[100],xx[100],yy[100],z[100];
bool c[10000];
long double ans=1e18;
void sze(long long x)
{
	long long cnt=n;
	while(x>0)
	{
		c[cnt--]=x%2;
		x/=2;
	}
}
int main()
{
	cin>>n>>s>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>xx[i]>>yy[i];
		z[i]=i;
	}
	do
	{
		long double ss=0.0;
		for(int i=1;i<=int(pow(2,n))-1;i++)
		{
			memset(c,0,sizeof(c));
			long long a=0,b=0;
			sze(i);
			ss=0.0;
			for(int i=1;i<=n;i++)
			{
//				cout<<a<<" "<<b<<" ";
				if(c[z[i]]==0)
				{
					ss=ss+sqrt((x[z[i]]-a)*(x[z[i]]-a)+(y[z[i]]-b)*(y[z[i]]-b))/s*1.0;
					ss=ss+sqrt((x[z[i]]-xx[z[i]])*(x[z[i]]-xx[z[i]])+(y[z[i]]-yy[z[i]])*(y[z[i]]-yy[z[i]]))/t*1.0;
					a=xx[z[i]];
					b=yy[z[i]];
				}
				else
				{
					ss=ss+sqrt((xx[z[i]]-a)*(xx[z[i]]-a)+(yy[z[i]]-b)*(yy[z[i]]-b))/s*1.0;
					ss=ss+sqrt((xx[z[i]]-x[z[i]])*(xx[z[i]]-x[z[i]])+(yy[z[i]]-y[z[i]])*(yy[z[i]]-y[z[i]]))/t*1.0;
					a=x[z[i]];
					b=y[z[i]];
				}
//				cout<<a<<" "<<b<<" "<<ss<<" "<<z[i]<<" "<<x[z[i]]<<" "<<y[z[i]]<<" "<<xx[z[i]]<<" "<<yy[z[i]]<<endl;
			}
//			cout<<i<<endl;
//			cout<<ss<<endl;
//			for(int i=1;i<=n;i++) cout<<c[z[i]]<<" ";
//			cout<<endl;
//			for(int i=1;i<=n;i++) cout<<z[i]<<" ";
//			cout<<endl;
			ans=min(ans,ss);
		}
	}while(next_permutation(z+1,z+n+1));
	cout<<fixed<<setprecision(20)<<ans<<endl;
	return 0;
}
2024/10/13 09:59
加载中...