题目链接
给n个物品的坐标， 和一个包裹的位置， 包裹不能移动。 每次最多可以拿两个物品， 然后将它们放到包里， 求将所有物品放到包里所需走的最小路程。
直接状压dp就好了。
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <map> #include <set> #include <string> #include <queue> #include <stack> #include <bitset> using namespace std; #define pb(x) push_back(x) #define ll long long #define mk(x, y) make_pair(x, y) #define lson l, m, rt<<1 #define mem(a) memset(a, 0, sizeof(a)) #define rson m+1, r, rt<<1|1 #define mem1(a) memset(a, -1, sizeof(a)) #define mem2(a) memset(a, 0x3f, sizeof(a)) #define rep(i, n, a) for(int i = a; i<n; i++) #define fi first #define se second typedef pair<int, int> pll; const double PI = acos(-1.0); const double eps = 1e-8; const int mod = 1e9+7; const int inf = 1061109567; const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; int n; int dp[1<<24], dis[25][25], b[1<<24], ans[500], cnt; pll a[25]; int main() {int x, y;cin>>a[0].fi>>a[0].se;cin>>n;a[n] = a[0];for(int i = 0; i<n; i++) {scanf("%d%d", &a[i].fi, &a[i].se);}for(int i = 0; i<=n; i++) {for(int j = 0; j<=n; j++) {dis[i][j] = (a[i].fi-a[j].fi)*(a[i].fi-a[j].fi)+(a[i].se-a[j].se)*(a[i].se-a[j].se);}}mem2(dp);dp[0] = 0;for(int i = 0; i<(1<<n); i++) {if(dp[i]==inf)continue;for(int j = 0; j<n; j++) {if((1<<j&i)==0) {for(int k = j; k<n; k++) {if((1<<k&i)==0) {int tmp = i|(1<<j)|(1<<k);int d = dis[j][k]+dis[n][j]+dis[n][k];if(dp[tmp]>dp[i]+d) {dp[tmp] = dp[i]+d;b[tmp] = i;}}}break;}}}cout<<dp[(1<<n)-1]<<endl;for(int i = (1<<n)-1; i!=0; i = b[i]) {int tmp = b[i]^i;ans[cnt++] = 0;for(int j = 0; j<n; j++) {if((1<<j)&tmp) {ans[cnt++] = j+1;}}}ans[cnt++] = 0;for(int i = cnt-1; i>=0; i--) {printf("%d ", ans[i]);}return 0; }
