ABC E题求hack
  • 板块学术版
  • 楼主liuyufeng1
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/10/23 11:10
  • 上次更新2023/10/27 06:21:57
查看原帖
ABC E题求hack
368515
liuyufeng1楼主2022/10/23 11:10

可怜可怜孩子吧,已经调了几个小时了

#include<bits/stdc++.h>
using namespace std;

const int maxn = 20;
const double inf = 1e18;

double dis(int sx, int sy, int ex, int ey){
	return sqrt(abs(sx - ex) * abs(sx - ex) + abs(sy - ey) * abs(sy - ey));
}

int n, m;
double x[maxn], y[maxn], speed, ans;
double f[maxn][1<<maxn]; //当前在第i个,城市状态为mask,速度为2^__builtin_popcount(mask>>n) 

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 0; i < n + m; i++) cin >> x[i] >> y[i];
	for(int i = 0; i < n + m; i++)
		for(int mask = 0; mask < 1 << (n + m); mask++) f[i][mask] = inf;
	for(int i = 0; i < n + m; i++) f[i][1<<i] = dis(0, 0, x[i], y[i]); 	
	
	for(int mask = 1; mask < 1 << (n + m); mask++){
		speed = pow(2, __builtin_popcount(mask >> n)); 
//		cout << speed << endl;
		for(int i = 0; i < n + m; i++) if((mask >> i) & 1){
			for(int j = 0; j < n + m; j++) if(!((mask >> j) & 1)){
				f[j][mask^(1<<j)] = fmin(f[j][mask^(1<<j)], f[i][mask] + dis(x[i], y[i], x[j], y[j]) / speed);
			}
		}	
	}
	
	ans = inf;
	for(int i = 0; i < n + m; i++)
		for(int mask = (1 << n) - 1; mask < 1 << (n + m); mask += 1 << n){
			speed = pow(2, __builtin_popcount(mask >> n));
			ans = fmin(ans, f[i][mask] + dis(0, 0, x[i], y[i]) / speed);
		}
		
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}

2022/10/23 11:10
加载中...