题解 | #收集纸片#

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define endl '\n'
using namespace std;
using pii = pair<int,int>;
const int maxn = 11;
int dp[1<<maxn][maxn];
int g[maxn][maxn];

void solve() {
    vector<pii> num(10+1);
    int w,h;cin >> w >> h;
    int a,b;cin >> num[0].first >> num[0].second;
    int n;cin >> n;
    memset(dp,0x3f,sizeof(dp));
    dp[1][0] = dp[0][0] = 0;
    for(int i = 1;i<=n;i++) {
        cin >> num[i].first >> num[i].second;
    }
    for(int i = 0;i<=n;i++) {
        for(int j = 0;j<=n;j++) {
                g[i][j] = abs(num[i].first-num[j].first)+abs(num[i].second-num[j].second);
        }
    }
    for(int s = 0;s<=(1<<(n+1))-1;s++) {
        for(int v = 0;v<=n;v++) {
            for(int u = 0;u<=n;u++) {
                if(s>>u & 1) dp[s][v] = min(dp[s][v],dp[s^(1<<u)][u]+g[u][v]);
            } 
        }
    }
    int ans = INF;
    for(int i = 1;i<=n;i++) {
        ans = min(ans,dp[(1<<(n+1))-1][i]+g[i][0]);
    }
    cout <<"The shortest path has length "<< ans << endl;;
}

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;cin >> t;
    while(t--) {
        solve();
    }
}

使用状态压缩dp，和TSP问题类似，时间复杂度为