poj 3311（状态压缩DP）
题意：一个人送披萨从原点出发，每次不超过10个地方，每个地方可以重复走，给出这些地方之间的时间，求送完披萨回到原点的最小时间。
解析：类似TSP问题，但是每个点可以重复走，先用floyd预处理每个点两两之间的最短距离，然后用状态压缩DP求出走完所有点后回到原点的最短距离，用一个二进制数表示城市是否走过。
状态表示：dp[i][j]表示到达j点状态为i的最短距离
状态转移方程：dp[i][j]=min(dp[i][j],dp[j'][k]+dis[k][j])，dis[k][j]为k到j的最短距离，dp[j'][k]为到达k的没经过j所有状态的最短距离
DP边界条件：dp[i][j]=dp[0][i]，i是只经过j的状态
枚举所有的状态，求解dp[i][j],然后再枚举走完所有的地方后的状态，求min（dp[(1<<n)-1][j]+dis[j][0]）就行了
AC代码如下：
#include<stdio.h>
#define INF 0x7fffffff
int dp[<<][],n,dis[][];
void floyd()
{
int i,j,k;
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
int min(int a,int b)
{
return a<b?a:b;
}
void DP()
{
int i,j,k;
for(i=;i< (<<n);i++) //枚举所有的状态
{
for(j=;j<=n;j++)
if(i==(<<(j-))) //状态i中只走过城市j
dp[i][j]=dis[][j];
else
{
if(i&(<<(j-))) //状态i中走过城市j和其他城市
{
dp[i][j]=INF;
for(k=;k<=n;k++)
{
if(j!=k && (i&(<<(k-)))) //枚举不是城市j的其他城市
//在没经过城市j的状态中，寻找合适的中间点k使得距离更短
dp[i][j]=min(dp[i][j],dp[i^(<<(j-))][k]+dis[k][j]);
}
}
}
}
int ans=INF;
for(i=;i<=n;i++) //枚举走完所有城市的状态，求回到原点的最短的距离
ans=min(ans,dp[(<<n)-][i]+dis[i][]);
printf("%d\n",ans);
}
int main()
{
int i,j;
while(scanf("%d",&n)&&n)
{
for(i=;i<=n;i++)
for(j=;j<=n;j++)
scanf("%d",&dis[i][j]);
floyd(); //预处理求出每个点两两之间的最短距离
DP();
}
return ;
}