题目链接：http://poj.org/problem?id=3311
题意：一个人到一些地方送披萨，要求找到一条路径能够遍历每一个城市后返回出发点，并且路径距离最短。最后输出最短距离即可。注意：每一个地方可重复访问多次。
经典的状压dp，因为每次送外卖不超过10个地方，可以压缩。
由于题中明确说了两个城市间的直接可达路径（即不经过其它城市结点）不一定是最短路径，所以需要借助floyd首先求出任意两个城市间的最短距离。
然后，在此基础上来求出遍历各个城市后回到出发点的最短路径的距离，即求解TSP问题。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1e5+;
const int INF=0x3f3f3f3f; int dp[<<][];
int d[][];
int n; void floyd() ///多源最短路，任意两点之间的距离都是最短的
{
for(int k=; k<=n; k++)
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
} ///dp[i][j]表示已经走过的城市为i，当前所在的城市为j的最短路程。
///相应的状态转移方程为dp[i][j]=min(dp[i^(1<<j)][k]+d[k][j]);
///i^(1<<j)的意思是将j这个城市从i状态中去掉。 d[k][j] 是k和j之间的距离。
void DP()
{
for(int i=; i<(<<n); i++)
for(int j=; j<=n; j++)
{
int tmp=<<(j-);
if(tmp==i) dp[i][j]=d[][j];
else if(tmp&i)
{
dp[i][j]=INF;
for(int k=; k<=n; k++)
if(k!=j && (i&(<<(k-))))
dp[i][j]=min(dp[i][j],dp[i^tmp][k]+d[k][j]);
}
}
int x=(<<n)-;
int ans=INF;
for(int i=; i<=n; i++)
ans=min(ans,dp[x][i]+d[i][]);
printf("%d\n",ans);
} int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)== && n)
{
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
scanf("%d",&d[i][j]); floyd();
DP();
}
return ;
}