Niuke monthly race 22- collect pieces of paper

D

The question ：
It's just one. n*m The matrix of ,n and m all <=20, And then there's the most 10 There's a piece of paper somewhere , Now let's take you from your initial position , The shortest distance to return to the original position after picking up all the pieces of paper .

reflection ：
At that time, I saw n Very small , Just want to press . I've seen a lot of things recently . Then I don't think it's easy to write , In fact dfs Enumeration method or next_permutation Just go . I chose dfs Because I thought this would happen , From the initial point to a The paper returns to its original point , Until then b Paper, etc , It is the case that the middle will return to the initial point first , But this topic will not be like this , Because it must be a straight line , The straight line between two points is the shortest , If it's a picture, it's not necessarily . The main thing is to look at the pressure dp How is it written .

Code ：

dfs( So when the title is a picture )：

int T,n,m,k;
int minn;
PII va[N];
int vb[N];
int vis[M];

void dfs(int now,int sum,int cnt)
{
    
	if(cnt==k+1)
	{
    
		sum += abs(va[0].fi-va[now].fi)+abs(va[0].se-va[now].se);
		minn = min(minn,sum);
		return ;
	}
	for(int i=0;i<=k;i++)
	{
    
		if(now==i) continue;
		if(vis[i]==0)
		{
    
			if(i!=0) vis[i] = 1;
			dfs(i,sum+abs(va[i].fi-va[now].fi)+abs(va[i].se-va[now].se),cnt+(i!=0));
			vis[i] = 0;
		}
	}
}

signed main()
{
    
	IOS;
	cin>>T;
	while(T--)
	{
    
		int a,b;
		cin>>n>>m>>a>>b>>k;
		for(int i=1;i<=k;i++) cin>>va[i].fi>>va[i].se;
		va[0] = {
    a,b};
		for(int i=0;i<=k;i++) vis[i] = 0;
		minn = inf;
		dfs(0,0,1);
		cout<<"The shortest path has length "<<minn<<"\n";
	}
	return 0;
}

 Pressure dp：
int T,n,m,k;
PII va[N];
int vb[M][M];
int dp[(1ll<<10)][15];

signed main()
{
    
	IOS;
	cin>>T;
	while(T--)
	{
    
		cin>>n>>m>>va[0].fi>>va[0].se>>k;
		for(int i=1;i<=k;i++) cin>>va[i].fi>>va[i].se;
		for(int i=0;i<=k;i++)
		{
    
			for(int j=0;j<=k;j++)
			vb[i][j] = abs(va[i].fi-va[j].fi)+abs(va[i].se-va[j].se);
		}
		for(int i=0;i<(1ll<<n);i++)
		{
    
			for(int j=0;j<=n;j++)
			dp[i][j] = inf; // All initialization inf
		}
		for(int i=1;i<=n;i++) dp[1ll<<(i-1)][i] = vb[0][i]; // When the last point is i, And the state of all points 1ll<<(i-1) The weight of the time . such as i==3, that dp[100][1] This state is like this .
		for(int i=0;i<(1ll<<n);i++)
		{
    
			for(int j=1;j<=n;j++)
			{
    
				if((i>>(j-1)&1)) continue;
				for(int k=1;k<=n;k++)
				{
    
					if((i>>(k-1)&1)==0) continue; //j yes 0, from k Transfer of ,k by 1.
					dp[i+(1ll<<(j-1))][j] = min(dp[i+(1ll<<(j-1))][j],dp[i][j]+vb[k][j]);
				}
			}
		}
		int minn = inf;
		for(int i=1;i<=k;i++) minn = min(minn,dp[i][(1ll<<n)-1]+vb[i][0]); // When all are achieved , And then finally i A weight .
		cout<<"The shortest path has length "<<minn<<"\n";
	}
	return 0;
}

General section ：
Attention to detail , Think more , A lot of summary .