问题来源：刘汝佳《算法竞赛入门经典--训练指南》 P61 问题9：
问题描述：有n(n<=15)个城市，两两之间均有道路直接相连，给出每两个城市i和j之间的道路长度L[i][j]，求一条经过每个城市一次且仅一次，最后回到起点的路线，使得经过的道路总长度最短(城市编号为0~n-1)。
分析： 1.因为最后走的路线为一个环，可以设城市0为起点城市。
2.将每个城市看作二进制的一个位(1代表有，0代表没有)，则数k可以表示一些城市的集合(例如k=13，二进制表示为1101，表示城市0,2,3的集合)，我们可以求得k<=2^15-1,令 aim=2^15-1;
3.dp[k][j]表示经过了k集合中的所有城市并且以j城市为终点的路径的最小值。
则dp[k][j] = Min{dp[k][j],dp[k-j][i]+dis[i][j] | (0<=i<=n-1 && i属于集合k)};(其中k-j表示集合k中去掉数j后的集合(所以j应该是集合k中的元素))，
例题链接：http://acm.fzu.edu.cn/problem.php?pid=2186
例题： fzu 2186
Problem 2186 小明的迷宫
Accept: 88 Submit: 270
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
小明误入迷宫，塞翁失马焉知非福，原来在迷宫中还藏着一些财宝，小明想获得所有的财宝并离开迷宫。因为小明还是学生，还有家庭作业要做，所以他想尽快获得所有财宝并离开迷宫。
Input
有多组测试数据。
每组数据第一行给出两个正整数n,m(0<n,m<=100)。代表迷宫的长和宽。
接着n行，每行m个整数。正数代表财宝(财宝的个数不超过10)；负数代表墙，无法通过；0代表通道。
每次移动到相邻的格子，所花费的时间是1秒。小明只能按上、下、左、右四个方向移动。
小明的初始位置是（1,1）。迷宫的出口也在（1,1）。
Output
输出获得所有财宝并逃出迷宫所花费的最小时间，如果无法完成目标则输出-1。
Sample Input
Sample Output
Source
FOJ有奖月赛-2015年03月
#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;
#define N 105
#define INF 0x3fffffff int m,n;
int map[N][N],mark[N][N];
int dis[][],flag[],dist[];
int dir[][] = {{-,},{,},{,-},{,}}; int dp[][],b[];
int inline Min(int a,int b){ return a<b?a:b; } struct Point
{
int x,y;
} point[]; struct node
{
int x,y;
int length;
}; void DFS(int start,int x,int y,int length)
{
int i,k;
int x1,y1;
queue<node> q;
node cur,next;
cur.x = x;
cur.y = y;
cur.length = ;
q.push(cur);
while(!q.empty())
{
cur = q.front();
q.pop();
for(i=; i<; i++)
{
next.x = x1 = cur.x+dir[i][];
next.y = y1 = cur.y+dir[i][];
next.length = cur.length+;
if(x1<= || x1>n || y1<= || y1>m || mark[x1][y1]!= || map[x1][y1]<)
continue;
if(map[x1][y1]>)
{
k = map[x1][y1];
dis[start][k] = dis[k][start] = next.length;
}
mark[x1][y1] = ;
q.push(next);
}
}
} int main()
{
int ans;
int i,j,k,num,l;
b[] = ;
for(i=; i<; i++) //b[i]存的2^i
b[i] = b[i-]*;
while(scanf("%d %d",&n,&m)!=EOF)
{
num = ;
for(i=; i<=n; ++i)
{
for(j=; j<=m; j++)
{
scanf("%d",&map[i][j]);
if(i== && j==&& map[i][j]>) num--;
if(map[i][j]>) map[i][j]= num++;
else if(map[i][j]<) map[i][j]=-;
}
}
if(map[][]<)
{
printf("-1\n");
continue;
}
map[][] = ;
for(i=; i<=n; ++i)
{
for(j=; j<=m; j++)
{
if(map[i][j]>)
{
k = map[i][j];
point[k].x = i, point[k].y = j;
} }
}
for(i=; i<num; i++)
{
for(j=; j<num; j++)
dis[i][j] = INF;
dis[i][i]= ;
}
for(i=; i<num; i++) //以每个点为起点广搜，求出任意两点间的最短距离
{
memset(mark,,sizeof(mark));
mark[point[i].x][point[i].y] = ;
DFS(i,point[i].x,point[i].y,);
}
num--; //宝藏编号为1~num
int tt = ;
for(i=; i<=num; i++)
{
if(dis[][i]==INF) //只要存在一个INF，表示至少有一个宝藏不可达，输出-1
tt = ;
}
if(tt==)
{
printf("-1\n");
continue;
}
int aim =b[num+]-;//y因为从2^1开始到2^num,则aim = 2^(num+1)-1-2^0
for(i=; i<=aim; i++)
{
for(j=; j<=num; j++)
dp[i][j] = INF;
}
dp[][] = ;
for(l=; l<=aim; l++) //一个集合l
{
for(i=; i<=num; i++)
{
for(j=; j<=num; j++)
{
if(i==j) continue;
if((b[i]&l)==) continue; //必须满足i 在集合l中，不满足，跳过，
if((b[j]&l)==) continue; //必须满足j不在集合l中，不满足，跳过，
if(dp[l][i]==INF) continue;
dp[l|b[j]][j]=Min(dp[l|b[j]][j],dp[l][i]+dis[i][j]);
}
}
}
ans = INF;
for(i=; i<=num; i++)
ans = Min(ans,dp[aim][i]+dis[i][]);
printf("%d\n",ans);
}
return ;
}