二进制枚举

实现\(N*(2^N)\)的暴力枚举

核心代码：

int n;
for(int i=0;i<(1<<n);i++){
  for(int j=0;j<i;j++){
    if(i&(1<<j)) //可以枚举2^n的所有情况
    else //如果有两种枚举（比如起点到终点 、终点到起点）
  }
}

例题:https://atcoder.jp/contests/abc374/tasks/abc374_d
\(O(N!*2^N)\)

#include<bits/stdc++.h>
#define endl '\n'
#define lowbit(x) (x&-x)
using namespace std;
const double pi=acos(-1);
typedef pair<int,int> pii;
long double dis(pii l,pii r){
	long double dx=(r.first-l.first)*(r.first-l.first);
	long double dy=(r.second-l.second)*(r.second-l.second);

	return sqrtl(dx+dy);
}

void solve(){
	int n,s,t;cin>>n>>s>>t;
	vector<pii> a(n),b(n);
	vector<int> p;
	for(int i=0;i<n;i++){
		cin>>a[i].first>>a[i].second>>b[i].first>>b[i].second;	
		p.push_back(i);
	}
	long double ans=1e18;
	do{
		for(int i=0;i<(1<<n);i++){
			long double res=0.0;
			pii tem={0,0};
			for(int j=0;j<n;j++){
				int idx=p[j];
				if(i&(1<<j)){
					res+=(dis(tem,a[idx])/(long double)s);
					res+=(dis(a[idx],b[idx])/(long double)t);
					tem=b[idx];
				}
				else{
					res+=(dis(tem,b[idx])/(long double)s);
					res+=(dis(b[idx],a[idx])/(long double)t);
					tem=a[idx];
				}
			}
			ans=min(ans,res);
		}
	}while(next_permutation(p.begin(),p.end()));
	printf("%.20Lf\n",ans);
}
signed main(){
	//ios::sync_with_stdio(false); cin.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--) solve();
	return 0;
}