提出 #35879803

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const long double inf = 1e18;
int n, m;
long double f[1 << 13][1 << 5][18], v[20];
// 0 ~ n - 1
// n ~ n + m - 1
struct node {
	long double x, y;
} a[20], b[20];
long double getdis(int x, int y) {
	long double x1, x2, y1, y2;
	if(x < n) {
		x1 = a[x].x;
		y1 = a[x].y;
	}
	else {
		x1 = b[x - n].x;
		y1 = b[x - n].y;
	}
	if(y < n) {
		x2 = a[y].x;
		y2 = a[y].y;
	}
	else {
		x2 = b[y - n].x;
		y2 = b[y - n].y;
	}
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	n++;
	for(int i = 0; i < m; i++) {
		cin >> b[i].x >> b[i].y;
	}
	for(int s = 0; s < (1 << n); s++) {
		for(int t = 0; t < (1 << m); t++) {
			for(int i = 0; i < n + m; i++) {
				f[s][t][i] = inf;
			}
		}
	}
	v[0] = 1;
	for(int i = 1; i <= m; i++) {
		v[i] = v[i - 1] * 2;
	}
	f[1][0][0] = 0;
	for(int s1 = 0; s1 < (1 << n); s1++) {
		for(int s2 = 0; s2 < (1 << m); s2++) {
			for(int i = 0; i < n + m; i++) {
				if(f[s1][s2][i] == inf) {
					continue;
				}
				long double t = v[__builtin_popcount(s2)];
				for(int j = 0; j < n; j++) {
					if(s1 >> j & 1) {
						continue;
					}
					f[s1 | (1 << j)][s2][j] = min(f[s1 | (1 << j)][s2][j], f[s1][s2][i] + getdis(i, j) / t);
				}
				for(int j = 0; j < m; j++) {
					if(s2 >> j & 1) {
						continue;
					}
					f[s1][s2 | (1 << j)][j + n] = min(f[s1][s2 | (1 << j)][j + n], f[s1][s2][i] + getdis(i, j + n) / t);
				}
			}
		}
	}
	long double ans = inf;
	for(int s = 0; s < (1 << m); s++) {
		long double t = v[__builtin_popcount(s)];
		for(int i = 0; i < n + m; i++) {
			ans = min(ans, f[(1 << n) - 1][s][i] + getdis(i, 0) / t);
		}
	}
	printf("%.10Lf\n", ans);
	return 0;
}

提出情報

ジャッジ結果