A、收集纸片

状态压缩dp

）当初小白赛可以过这道题，是因为前几天做过一题比较类似的小松鼠找松果的题目……

回到这个题目，题目给出的地图很小最大也就是可以考虑二进制枚举。
那么就开一个数组代表以为终点把二进制表示中的1走过一遍的最小花费。
那么第一步预处理每两个点之间的距离，以及和源点之间的距离。
初始化只走一个点的值为从源点去对应点的起始花费。
再去二进制枚举我能选择的终点全部的情况，对于枚举的状态来说，如果有一个点我可以去，那么从这个点开始更新各个我这次不打算去的终点，因为我要搜集全部的纸片，相当于枚举决策点k。
最后再把从最终留在位置花费加上回去起点花费，取最小值就是题目要求的。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 20;
const int N = 25;
const int M = 65536;
int x[N], y[N];
int maps[N][N];
int dp[N][M];
int maxz; //状态压缩dp

void updata(int& x, int y) {
    if (x > y)
        x = y;
}

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        cin >> x[0] >> y[0];
        int num;
        cin >> num;
        for (int i = 1; i <= num; ++i)   cin >> x[i] >> y[i];
        for (int i = 0; i <= num; ++i)
            for (int j = 0; j <= num; ++j)
                maps[i][j] = abs(x[i] - x[j]) + abs(y[i] - y[j]);
        maxz = (1 << num) - 1;
        for (int i = 0; i <= maxz; ++i)
            for (int j = 0; j <= num; ++j)
                dp[j][i] = INF;
        for (int i = 1; i <= num; ++i)
            dp[i][1 << (i - 1)] = maps[0][i];
        for (int i = 0; i <= maxz; ++i) {
            for (int j = 1; j <= num; ++j)
                if (i & (1 << (j - 1))) {
                    for (int k = 1; k <= num; ++k)
                        if (!(i & (1 << (k - 1))))
                            updata(dp[k][i + (1 << (k - 1))], dp[j][i] + maps[j][k]);
                }
        }
        int ans = INF;
        for (int i = 1; i <= num; ++i)
            updata(ans, dp[i][maxz] + maps[0][i]);
        cout << "The shortest path has length " << ans << endl;
    }
    return 0;
}