P1433 吃奶酪帮忙看一下,RE了,改了一天,请大佬们帮我查查错,非常感谢!
#include <bits/stdc++.h>
using namespace std;
int n;
double a[20], b[20], dp[(1 << 15) + 5][20], ans = 1e9;
bool used[20];
double dis(int x,int y)
{
sqrt((a[x] - a[y]) * (a[x] - a[y]) + (b[x] - b[y]) * (b[x] - b[y]));
}
void dfs(int t, int now, double s, int bb)
{
if(s > ans) return;
if(t == n)
{
ans = min(ans, s);
return ;
}
for(int i = 1; i <= n; i++)
{
if(used[i] == 0)
{
int p = bb + (1 << (i - 1));
if(dp[p][i] != 0 && dp[p][i] <= s + dis(now, i)) continue;
used[i] = 1;
dp[p][i] = s + dis(now, i);
dfs(t + 1, i, dp[p][i], p);
used[i] = 0;
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i], &b[i]);
dfs(0, 0, 0, 0);
printf("%.2lf\n", ans);
return 0;
}