WA了几个点,看不出来问题在哪
#include <bits/stdc++.h>
using namespace std;
const int MAX = 17;
int n;
pair<double, double> arr[MAX];
double ans = INFINITY; // ans初始化为无限大
double dis_all[MAX][MAX]; // 相当于邻接矩阵
double dp[MAX][1 << MAX]; // 用于状压dp
double dis(const pair<double, double> &a, const pair<double, double> &b) // 计算两点间的距离
{
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i, j;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i].first >> arr[i].second;
}
memset(dis_all, 127, sizeof(dis_all)); // 初始化邻接矩阵中所有距离为正无穷
memset(dp, 127, sizeof(dp)); // 初始化dp数组中所有距离为正无穷
for (i = 0; i <= n; i++) // 处理出每个点到其余所有点的距离
{
for (j = 0; j < i; j++)
{
dis_all[i][j] = dis_all[j][i] = dis(arr[i], arr[j]);
}
}
for (i = 1; i <= n; i++) // 初始化从原点直接到每个奶酪的状态
{
dp[i][1 << (i - 1)] = dis_all[0][i];
}
for (int k = 1; k < (1 << n); k++) // 枚举每个二进制状态
{
for (i = 1; i <= n; i++) // 枚举终点
{
if (k & (1 << (i - 1)) == 0) // 如果当前状态不包含该终点则跳过
{
continue;
}
for (j = 1; j <= n; j++) // 枚举起点
{
if (i == j || (k & (1 << (j - 1)) == 0)) // 如果当前状态不包含该起点,或起点终点一样则跳过
{
continue;
}
dp[i][k] = min(dp[i][k], dp[j][k - (1 << (i - 1))] + dis_all[j][i]); // 状态转移方程
}
}
}
for (i = 1; i <= n; i++)
{
// cout << dp[i][(1 << n) - 1] << '\n';
ans = min(ans, dp[i][(1 << n) - 1]);
}
cout << fixed << setprecision(2) << ans;
// printf("%.2lf", ans);
return 0;
}