题目
思路
前排提示：这里的下标全部从(1)开始
思路怎么可能时二进制DP呢？这才第一章啊。
应该吧
然后我用了BFS暴力搜索。
首先，我们发现题目是一个无向完全图，虽然我做完还是不知道a[x,y]+a[y,z]>=a[x,z]有什么用其实这也不重要，我用BFS的管我屁事。好像DP的也无关紧要吧
都是从(0)开始那我们就不管了，因为要求每个点都走一遍，所以我们肯定要用某种方式把我们走过的点表示出来，没错，就是二进制，而这里(n<=20)，所以二进制第(i)位就代表了这个点有没有走过，同时也有一个很重要的信息还要记录就是我们当前走到了哪个点，不难想出，利用这两个信息就足以用这个路径进行转移了，什么，你说有很多条路径满足这个信息？这就是压缩信息的精髓了，把一些类似的路径取一个最小值进行转移，同时不影响答案（插头DP其实也是类似的思路）。
仔细想想你会发现，满足同两个信息的一些路径在转移上都是一样的，且最后尽可能是走过的边权和最小的路径可以转移成功，所以只要用边权和最小的路径代表这些路径就行了。
然后对于(f[i][j])（(i)记录路径，(j)表示目前到了哪个点）的转移就是：
(f[i+(1<<(k-1))][k]=f[i][j]+a[j][k])。
然后就可以愉快的BFS啦。
但是BFS比较容易BFS，如果想要降空间的话还是用DP吧，但是时间复杂度是一样的，只不过DP利用二进制的一个性质：走过(k)个点的路径转移完后，(k+1)个点的路径的(f)值就全部出来了，所以只要把含有(k)个(1)的全部(f)转移完之后去转移(k+1)个(1)就行了，当然，DP也可以找这条路径是由哪些路径转移来的进行DP，时间复杂度也是一样的（如(f[3][2])会主动去找(f[1][1])来更新自己），只不过一个是更新别人，一个是找别人更新自己罢了（还有一些更神奇的转移顺序我就不说了）。
代码
#include<cstdio>
#include<cstring>
#define N 22
#define M 1100000
using namespace std;
int n,a[N][N],f[M][N]/*M表示走过的装填,N表示目前所在的位置*/;
struct qmq
{
int x,y;/*y表示状态，x表示位置*/
}list[16000000];int head,tail;
inline int mymin(int x,int y){return x<y?x:y;}
int main()
{
scanf("%d",&n);
int limit=(1<<n)-1;
for(int i=1;i<=limit;i++)
{
for(int j=1;j<=n;j++)f[i][j]=999999999;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
}
list[1].x=1;list[1].y=1;f[1][1]=0;
head=1;tail=1;
while(head<=tail)
{
qmq x=list[head++];
for(int i=1;i<=n;i++)
{
if((x.y&(1<<(i-1)))==0)//没走过
{
qmq now;now.y=x.y^(1<<(i-1));now.x=i;
if(f[now.y][now.x]==999999999)list[++tail]=now;//没有走过就加入队列
f[now.y][now.x]=mymin(f[now.y][now.x],f[x.y][x.x]+a[x.x][i]);
}
}
}
int ans=f[limit][n];
printf("%d
",ans);
return 0;
}