题意：一个送外卖的人，要将外卖全部送去所有地点再回到店离，求最短路。（可以重复经过边）
思路：由于可重复走某些边，所以先求各个点的最短路，再TSP
dp[i][s] 表示目前在i点还需要遍历s集合后回到0点的最短路径
边界条件就是dp[i][0]=dis[i][0]
//196 KB0 msC++1190 B#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;int map[15][15];int dis[15][15];int n;int dp[15][1<<10];int main(){while(scanf("%d",&n),n){memset(dis,0x3f,sizeof(dis));for(int i=0;i<=n;i++)for(int j=0;j<=n;j++){scanf("%d",&map[i][j]);dis[i][j]=map[i][j];}for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);memset(dp,0x3f,sizeof(dp));for(int i=1;i<=n;i++) dp[i][0]=dis[i][0];for(int s=0;s<(1<<n);s++)for(int u=0;u<n;u++)if(((1<<u)&s)==0)for(int v=0;v<n;v++)if((1<<v)&s)dp[u+1][s]=min(dp[u+1][s],dp[v+1][s^(1<<v)]+dis[u+1][v+1]);int g=(1<<n)-1;for(int v=0;v<n;v++)if((1<<v)&g)dp[0][g]=min(dp[0][g],dp[v+1][g^(1<<v)]+dis[0][v+1]);printf("%d\n",dp[0][g]);}return 0;}
，成功是什么?就是走过了所有通向失败的路.只剩下一条路.那就是成功的路.
