状压DP，对于这种范围给到20的，1<<20并不大，dp[i][j]中i代表状态，表当前二十个二进制位中，有多少点已经走过，j代表的是当前状态中最后的点什么，我们维护这个二维数组，就能得到答案dp[(1<<n)-1][n-1]，如何转移呢？？？很简单，我们知道，一个状态i，由另外一个状态转移过来，一定是另外一个状态的二进制位的点，走到了新的二进制位0的点，造成了那个点的状态变成二进制状态位1，从而产生了新的状态，那么其实很简单了，直接转移就行。
#include <bits/stdc++.h> #define LL long long using namespace std; int n; int maps[30][30]; const int maxx = (1<<20)+2; int d[maxx][20]; const int INF = 0x3f3f3f3f; int main(){ while(~scanf("%d",&n)){ for (int i=0;i<n;i++){ for (int j=0;j<n;j++){ scanf("%d",&maps[i][j]); } } memset(d,0x3f,sizeof(d)); d[1][0]=0; for(int i=1;i<(1<<n);i++){ for (int j=0;j<n;j++){ if((i>>j)&1){ //代表走过的点中有第j号点，i的第j位置的二进制位不为0 for (int k=0;k<n;k++){ if((i^(1<<j))>>k & 1){ d[i][j]=min(d[i][j],d[i^(1<<j)][k]+maps[j][k]); } } } } } printf("%d\n",d[(1<<n)-1][n-1]); } return 0; }