CF8C Looking for Order（状压DP）

题意：

给出平面上的一些点，点之间的距离是欧几里得距离的平方。

女孩从起点开始，目标是把所有的点上的物品运送回起点，规定手上不能同时携带两个物品。

询问最快的时间和路线。

题解：

#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
int dp[1<<24];
int pre[1<<24];
int g[maxn][maxn];
int x[maxn];
int y[maxn];
int n;
int dfs1 (int u) {
    if (dp[u]!=-1) return dp[u];
    dp[u]=1e9;
    for (int i=0;i<n;i++) {
        if (u&(1<<i)) {
            int nxt=dfs1(u^(1<<i));
            if (dp[u]>nxt+g[n][i]+g[i][n]) {
                dp[u]=nxt+g[n][i]+g[i][n];
                pre[u]=u^(1<<i);
            }
            for (int j=i+1;j<n;j++) {
                if (u&(1<<j)) {
                    nxt=dfs1(u^(1<<i)^(1<<j));
                    if (dp[u]>nxt+g[n][i]+g[i][j]+g[j][n]) {
                        dp[u]=nxt+g[n][i]+g[i][j]+g[j][n];
                        pre[u]=u^(1<<i)^(1<<j);
                    }
                }
            }
            break;
        }
    }
    return dp[u];
}
int dfs2 (int u) {
    if (u) {
        for (int i=0;i<n;i++) {
            if ((u^pre[u])&(1<<i))
                cout<<i+1<<" ";
        }
        cout<<"0 ";
        dfs2(pre[u]);
    }
}
void solve () {
    int X,Y;
    cin>>X>>Y>>n;
    x[n]=X;
    y[n]=Y;
    for (int i=0;i<n;i++) cin>>x[i]>>y[i];
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++) 
            g[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    cout<<dfs1((1<<n)-1)<<'
';
    cout<<"0 ";
    dfs2((1<<n)-1);
    
}
int main () {
    solve();
}