原题在这
题目大意是在一个直角坐标系内,出生在原点,给n,m个点,前n个点需要全部踩过一次,然后回到原点。剩下那m个点,可踩可不踩,但是经过后速度翻倍(只有第一次经过算数),初速速度为1。求最短时间。
1 ≤ n ≤ 12
0 ≤ m ≤ 5
坐标x,y的绝对值均小于10000.
给出的坐标不重合,而且不为原点
这是我的代码,wa了一个点wawa
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 18;
const double inf = 1e18;
struct node
{
int x, y;
node(int a, int b) : x(a), y(b) {}
node() {}
} p[maxn];
double dp[maxn][1 << maxn];
double dis[maxn][maxn];
double dist(node a, node b)
{
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
int n, m;
int cntt(int s)
{
int cnt = 0;
s >>= n;
for (int i = 0; i < m; i++)
{
if (s & (1 << i))
++cnt;
}
return cnt;
}
int judge(int s)
{
for (int i = 0; i < n; i++)
{
if (!(s & (1 << i)))
return false;
}
return true;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
int sum = m + n;
for (int i = 0; i < sum; ++i)
{
cin >> p[i].x >> p[i].y;
}
for (int i = 0; i < sum; ++i)
for (int j = i + 1; j < sum; ++j)
dis[i][j] = dis[j][i] = dist(p[i], p[j]);
for (int i = 0; i < sum; ++i)
for (int s = 0; s < (1 << sum); ++s)
dp[i][s] = inf;
for (int i = 0; i < n + m; ++i)
dp[i][1 << i] = dist(node(0, 0), p[i]);
double minx = inf;
for (int s = 1; s < (1 << sum); ++s)
for (int i = 0; i < sum; ++i)
{
if (s & (1 << i))
{
int v = pow(2, __builtin_popcount(s >> n));
bool flag = judge(s);
for (int j = 0; j < sum; j++)
{
if (i != j && (1 << j) & s)
{
if (i >= n)
v /= 2;
dp[i][s] = min(dp[i][s], dp[j][s - (1 << i)] + dis[i][j] / v);
if (i >= n)
v *= 2;
if (flag)
minx = min(minx, dp[i][s] + dist(p[i], node(0, 0)) / v);
}
}
}
}
cout << fixed << setprecision(10) << minx;
return 0;
}