Introduction to ACM [TSP problem]

Travel agent problem , namely TSP Problem is one of the famous problems in the field of mathematics .
Suppose there is a traveling salesman to visit n Cities , He has to choose the path to take , The path limit is that each city can only visit once , And finally to return to the original city of departure .
The goal of path selection is to require the path distance to be the minimum of all paths .

This is a very classic question , Generally in ACM Or common in interview algorithm questions .
Here is the shape pressing DP To solve the problem .

Example 1 :

You don't have to come back here , And fixed the starting point and ending point .
f[i][j] It means i State, The end is j Minimum cost of

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int g[N][N],f[1<<21][25],n;
int main(void)
{
    
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++) cin>>g[i][j];
    memset(f,0x3f,sizeof f);
    f[1][0]=0;
    for(int i=0;i<(1<<n);i++)
    {
    
        for(int j=0;j<n;j++)
        {
    
            if(i>>j&1)
            {
    
                for(int k=0;k<n;k++)
                {
    
                    int temp=i-(1<<j);
                    if(temp&1)
                    {
    
                        f[i][j]=min(f[i][j],f[i-(1<<j)][k]+g[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1];
    return 0;
}

Example 2 :

First floyd(), Then comes the classic model . There is no definite starting point and ending point .

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int g[N][N],f[1<<16][20],a[N];
int n,m,t;
int main(void)
{
    
	cin>>n>>m>>t;
	memset(f,0x3f,sizeof f);
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=n;i++) g[i][i]=0;
	for(int i=0;i<t;i++) cin>>a[i];
	while(m--)
	{
    
		int a,b,c; cin>>a>>b>>c;
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
	for(int i=0;i<t;i++) f[1<<i][i]=0;
	for(int i=0;i<(1<<t);i++)
	{
    
		for(int j=0;j<t;j++)
		{
    
			if(i>>j&1)
			{
    
				for(int k=0;k<t;k++)
				{
    
					if(i>>k&1)
					{
    
						f[i][j]=min(f[i][j],f[i-(1<<j)][k]+g[a[k]][a[j]]);
					}
				}
			}
		}
	}
	int ans=1e9;
	for(int i=0;i<t;i++) ans=min(ans,f[(1<<t)-1][i]);
	cout<<ans;
	return 0;
}