题解 | 收集纸片

直接dfs全排列所有可能，取最小值。

#include<bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
#define endl "\n"
#define vi(a) vector<int> 
#define vll(a) vector<long long> a
#define x first
#define y second
using namespace std;
const int NUM=10e5+7;
const pair<ll,ll> P[9]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
// const pair<ll,ll> P[6]={{-1,0},{1,0},{0,-1},{0,1},{0,0}};
ll X[5]={-1,1,0,0};
ll Y[5]={0,0,-1,1};
const ll MOD=1000000007;
ll ans=100000000000,n,k,ym,m,x,y;
string s;
ll bg,ed,sx,sy,sum;
bool f[1005];
pair<ll,ll> zp[15];
vll(db);
void dfs(int x,int l){
	// cout<<sum<<' ';
	if (x==n){
		// for (auto t:db){cout<<t<<' ';}
		sum+=abs(zp[l].x-sx);
		sum+=abs(zp[l].y-sy);
		ans=min(ans,sum);
		sum-=abs(zp[l].x-sx);
		sum-=abs(zp[l].y-sy);
		// cout<<sum+abs(zp[l].x-sx)+abs(zp[l].y-sx)<<endl;
		return ;
	}
	for (int i=1;i<=n;i++){
		if (!f[i]){
			f[i]=1;
			// cout<<zp[i].x<<' '<<zp[i].y<<' '<<zp[l].x<<' '<<zp[l].y<<endl;
			sum+=abs(zp[l].x-zp[i].x);
			sum+=abs(zp[l].y-zp[i].y);
			// cout<<sum<<endl;
			db.push_back(i);
			dfs(x+1,i);
			sum-=abs(zp[l].x-zp[i].x);
			sum-=abs(zp[l].y-zp[i].y);
			f[i]=0;
			db.pop_back();
		}
	}
	return ;
}
void solve()
{
	ans=100000000000;
	sum=0;
	cin>>bg>>ed;
	cin>>sx>>sy;
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>zp[i].x>>zp[i].y;
	}
	zp[0].x=sx;
	zp[0].y=sy;
	// for (int i=0;i<=n;i++){
	// 	cout<<zp[i].x<<' '<<zp[i].y<<endl;
	// }
	dfs(0,0);
	cout<<"The shortest path has length ";
	cout<<ans<<endl;
	return ;
}
int main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
	return 0;
}