dp[1][0] = 0;
for (i=3; i<(1<<n); i+=2) //枚举状态.最右为1号城市,遍历奇数就可以枚举所有状态了
for (j=1; j<n; j++) //枚举终点.扫一遍
if (i&(1<<j)) //判断是否合法.状态i是否可以以j为终点
{
temp = i – (1<<j);//表示没到j点前的状态
if (temp == 1)//若是从起点而来
{
dp[i][j] = dis[0][j];
continue;
}
for (dp[i][j]=MAX, k=0; k<n; k++) //枚举前一个点
if (i&(1<<k) && k != j) //判断是否合法
dp[i][j] = min(dp[i][j], dp[temp][k] + dis[k][j]);
}
ans = MAX;
for (i=1; i<n; i++) //遍历一遍求最终结果
ans = min(ans, dp[(1<<n)-1][i] + dis[i][0]);
printf(“%d\n”, ans);