给出一个有n个点的有向图，编号1～n，边权已经给出，询问最短hamilton路径，其定义为不重不漏地经过所有点以1为起点以n为终点的路径，(nleq 20)。
解
注意到数据范围很小，支持二进制压缩，为了压缩方便，将每个点的标号减1,然而递推方程里必然要表现终点，而要保证不重不漏，于是还要记录有哪些点已经被经过了，于是设(f[i][j])表示当前状态为i，以j为终点的路径，其中i的二进制第k位为1表示已经经过该点，反之，于是不难有(定义(w[i][j])为点i到点j的边权)
[f[i][j]=min_{k=0,j!=k&&i>>k&1}^{n-1}{f[iwedge 1<<j][k]+w[k][j]}(i>>j&1)
]
边界：(f[1][0]=0),其余负无限大
答案：(f[(1<<n)-1][n-1])
时间复杂度:(O(2^n imes n))
因为很难看出明显的阶段性，于是在考场尽量选择bfs（拓扑排序），dfs（记忆化搜索）实现，但是注意到求(f[i][j])其对应的决策点的第一维是在缩小的，于是可以以之为阶段进行枚举。
参考代码：
dfs
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
bool is[1048576][21];
int a[21][21],dp[1048576][21],n;
il int dfs(int,int);
template<class free>
il free Min(free,free);
int main(){
scanf("%d",&n);
for(int i(0),j;i<n;++i)
for(j=0;j<n;++j)
scanf("%d",&a[i][j]);
memset(dp,0x3f,sizeof(dp));
dp[1][0]=0,is[1][0]|=true;
printf("%d",dfs((1<<n)-1,n-1));
return 0;
}
template<class free>
il free Min(free a,free b){
return a<b?a:b;
}
il int dfs(int a,int b){
if(is[a][b])return dp[a][b];is[a][b]|=true;
for(int c(0);c<n;++c)
if(a>>c&1)dp[a][b]=Min(dp[a][b],dfs(a^(1<<b),c)+::a[c][b]);
return dp[a][b];
}
阶段实现（即循环）
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
using namespace std;
int a[21][21],dp[1048576][21];
template<class free>
il free Min(free,free);
int main(){
int n,li;scanf("%d",&n),li=1<<n;
for(int i(0),j;i<n;++i)
for(j=0;j<n;++j)
scanf("%d",&a[i][j]);
memset(dp,0x3f,sizeof(dp)),dp[1][0]=0;
for(int i(0),j,k;i<=li;++i)
for(j=0;j<n;++j)
if(i>>j&1)
for(k=0;k<n;++k){
if(k==j)continue;
if(i>>k&1)
dp[i][j]=Min(dp[i][j],dp[i^(1<<j)][k]+a[k][j]);
}printf("%d",dp[li-1][n-1]);
return 0;
}
template<class free>
il free Min(free a,free b){
return a<b?a:b;
}