旅行商问题(状态压缩dp)

int d[N][N];//图 int dp[1<<N][N];//记忆化搜索使用的数组 int rec(int S,int v)//表示已经访问过的节点集合为S，当前位置为v { if(dp[S][v]>=0) return dp[S][v]; if(S==(1<<n)&&v==0)//已经访问过所有的节点并回到0号点 return dp[S][v]=0; res=INF; for(u=0;u<n;u++) { if(!(S>>u&1))//下一步移动到顶点u { res=min(res,rec(S|1<<u,u)+d[v][u]); } } return dp[S][v]=res; } int main(void) { memset(dp,-1,sizeof(dp)); printf("%d\n",rec(0,0)); }