一不小心拿了运行时间最快qwq（2ms）（截止此时）

要求从一个初始位置开始，经过所有的纸片，最终再回到初始坐标，求走过的最短距离。

方法1：暴力枚举或dfs（2ms）

我们可以用求1~n的全排列，计算所有可能的走法，由于纸片数不超过10，所以走法最多只有10!种。

全排列求法见《算法竞赛进阶指南》中的0x02 递归实现排列型枚举，用dfs或next_permutation皆可

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define min(a,b) (a<b ? a:b)
int ans,n,a[12][2],d[12][12],p[11]= {0,1,2,3,4,5,6,7,8,9,10};
inline void calc() {//计算路径长
    int tmp=d[0][p[1]];//从初始位置开始
    for (int i=1; i<n; i++) {
        tmp+=d[p[i]][p[i+1]];
        if (tmp>ans) return;
    }
    ans=min(ans,tmp+d[p[n]][0]);//最终回到初始位置
}
int main() {
    int T,x,y;
    scanf("%d",&T);
    while(T--) {
        ans=0x3f3f3f3f;
        scanf("%d%d%d%d%d",&x,&y,&a[0][0],&a[0][1],&n);//a[0]是初始位置
        for (int i=1; i<=n; i++)
            scanf("%d %d",&a[i][0],&a[i][1]),p[i]=i;
        for (int i=0; i<=n; i++)
            for (int j=0; j<=n; j++)
                d[i][j]=abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]);
        do {
            calc();
        } while (next_permutation(p+1,p+n+1));//枚举1~n的全排列
        printf("The shortest path has length %d\n",ans);
    }
}

方法2：状压dp（2ms）

把每个纸片都不重不漏地恰好经过一次，很容易想到旅行商问题，即TSP问题（Traveling Salesman Problem）（每个城市只能拜访一次，而且最后要回到原来出发的城市。），可以用状压dp

具体可参考《算法竞赛进阶指南》中的0x01 最短Hamilton路径

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define min(a,b) (a<b ? a:b)
int ans,a[11][2],d[11][11],f[1<<11][11];
int main() {
    int T,n,x,y,lim;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d%d%d",&x,&y,&a[0][0],&a[0][1],&n);//a[0]是初始位置
        for (int i=1; i<=n; i++)
            scanf("%d %d",&a[i][0],&a[i][1]);
        for (int i=0; i<=n; i++)
            for (int j=0; j<=n; j++)
                d[i][j]=abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]);
        memset(f,0x3f,sizeof f),ans=0x3f3f3f3f;
        f[1][0]=f[0][0]=0,lim=(1<<(n+1))-1;
        for (register int i=0; i<=lim; i++)
            for (int j=0; j<=n; j++)
                if (i>>j&1)//最后一个经过的点
                    for (int k=0; k<=n; k++)
                        if (i>>k&1)//从k走到j
                            f[i][j]=min(f[i][j],f[i^(1<<j)][k]+d[k][j]);
        for (int i=1; i<=n; i++)
            ans=min(ans,f[lim][i]+d[i][0]);//把所有的纸片都经过后，最终找一条路径回到初始位置
        printf("The shortest path has length %d\n",ans);
    }
}