Hie with the Pie - POJ 3311

http://poj.org/problem?id=3311

The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deliveries. He will wait for 1 or more (up to 10) orders to be processed before he starts any deliveries. Needless to say, he would like to take the shortest route in delivering these goodies and returning to the pizzeria, even if it means passing the same location(s) or the pizzeria more than once on the way. He has commissioned you to write a program to help him.

Input

Input will consist of multiple test cases. The first line will contain a single integer n indicating the number of orders to deliver, where 1 ≤ n ≤ 10. After this will be n + 1 lines each containing n + 1 integers indicating the times to travel between the pizzeria (numbered 0) and the n locations (numbers 1 to n). The jth value on the ith line indicates the time to go directly from location i to location j without visiting any other locations along the way. Note that there may be quicker ways to go from i to jvia other locations, due to different speed limits, traffic lights, etc. Also, the time values may not be symmetric, i.e., the time to go directly from location i to j may not be the same as the time to go directly from location j to i. An input value of n = 0 will terminate input.

Output

For each test case, you should output a single number indicating the minimum time to deliver all of the pizzas and return to the pizzeria.

Sample Input

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

Sample Output

8

https://blog.csdn.net/V5ZSQ/article/details/47184813
题意是有n个城市(1~n)和一个披萨店(0),要求一条回路，从0出发，又回到0，而且距离最短 
Input 
多组输入，每组用例第一行为一个整数n表示成熟数量，之后为一个(n+1)*(n+1)矩阵表示n个城市和披萨店之间的距离矩阵，以n=0结束输入 
对于每组用例，输出最短距离 

TSP(旅行商)问题，首先不难想到用FLOYD先求出任意2点的距离dis[i][j]，接着枚举所有状态，用11位二进制表示10个城市和披萨店，1表示经过，0表示没有经过 定义状态dp[state][j]表示在state状态下，到达城市I的最优值,接着状态转移方程:dp[state][i] = min{dp[s^(1<<(i-1)][k]) + dis[k][i],dp[state][i])},(state^(1<<(i-1))表示未到达城市i的所有状态,1<=k<=n)。对于全1的状态，即state=(1<< n)-1则表示经过所有城市的状态，最终还需要回到披萨店0，那么最终答案就是min{dp[state][i]+dis[i][0]}

https://blog.csdn.net/sinat_35406909/article/details/77822005

用dp[i][j]表示从0号点出发，经过一些点之后状态为i,最后经过城市为j的最短时间。其中，i 用二进制表示是否经过n个点。

则dp[i][j]=min(dp[i^(1<<(j-1)][k]+dist[k][j])

http://my-zhang.github.io/blog/2014/04/20/dynamic-programming-with-bitmask/

POJ 3311. A basic TSP problem, however it requires the path start and end with the central point. In addition, floyd algorithm is needed to preprocess the distance matrix.

int dp[1<<N][N]; int d[N][N]; // distance matrix void input(int d[N][N], int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cin >> d[i][j]; } } } bool is_element(int bitmask, int index) { return bitmask == (bitmask | (1<<index)); } int dist(int i, int j) { return d[i+1][j+1]; } void floyd(int d[N][N], int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { for(int k = 0; k < n; k++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } } int main() { int n; while(cin >> n) { if(n == 0) { break; } /* get distance matrix. */ input(d, n+1); /* distance matrix preprocess. */ floyd(d, n+1); /* dp init. * All the path should start with the S. */ for(int i = 0; i < n; i++) { for(int k = 0; k < (1<<n); k++) { dp[k][i] = INF; } dp[1<<i][i] = dist(S, i); } /* dp stage. */ for(int i = 1; i < (1<<n); i++) { for(int j = 0; j < n; j++) { if(dp[i][j] != INF) { continue; } if(is_element(i, j)) { int min_dist = INF; for(int k = 0; k < n; k++) { if(is_element(i, k) && k != j) { if(min_dist == INF || min_dist > dp[i-(1<<j)][k] + dist(k, j)) { min_dist = dp[i-(1<<j)][k] + dist(k, j); } } } dp[i][j] = min_dist; } } } /* Choosing final result. * The complete path need to end with S */ int min_dist = INF; for(int i = 0; i < n; i++) { if(min_dist == INF || min_dist > dp[(1<<n)-1][i] + dist(i, S)) { min_dist = dp[(1<<n)-1][i] + dist(i, S); } } cout << min_dist << endl; } // testcase loop }

https://www.cnblogs.com/zzulipomelo/p/5328813.html
while(scanf("%d",&n)!=EOF,n) { for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) scanf("%d",&mapp[i][j]); for(int k=0; k<=n; k++) for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) mapp[i][j]=min(mapp[i][j],mapp[i][k]+mapp[k][j]); for(int s=0; s<=(1<<n)-1; s++) //先对1~n 的点枚举 { for(int i=1; i<=n; i++) { if(s&(1<<(i-1))) // 如果情况i在集合s中 { if(s == (1<<(i-1))) //如果当前的集合s与情况i相同，最有解是从0出发到达i，也是dp的边界情况 dp[s][i]=mapp[0][i]; else { dp[s][i]=inf; for(int j=1; j<=n; j++) { if(s & (1<<(j-1)) && i!=j) //枚举不是城市I的其他城市 { dp[s][i]=min(dp[s][i],dp[s^(1<<(i-1))][j]+mapp[j][i]); //在没经过城市i的状态中，寻找合适的中间点j使得距离更短 } } } } } } int ans=inf; // 找到从1~n的最短路之后，然后从每个点返回到0的距离 for(int i=1; i<=n; i++) { ans=min(ans,dp[(1<<n)-1][i]+mapp[i][0]); } printf("%d\n",ans); }


https://www.jianshu.com/p/104b220b5426

#include<cstdio>
#include<cstring>
using namespace std;
int mapp[11][11];
int dp[1<<13][13];
int n;
int main()
{
   while(~scanf("%d",&n)&&n)
   {
      memset(mapp,0,sizeof(mapp));
      memset(dp,-1,sizeof(dp));
       for(int i=0;i<=n;i++)
       {
           for(int j=0;j<=n;j++)
           {
               scanf("%d",&mapp[i][j]);
           }
       }
       for(int k=0;k<=n;k++)
       {
           for(int i=0;i<=n;i++)
           {
               for(int j=0;j<=n;j++)
               {
                         if(mapp[i][j]>mapp[i][k]+mapp[k][j])
                         {
                              mapp[i][j]=mapp[i][k]+mapp[k][j];
                         }

               }
           }
       }
       dp[1][0]=0;
       for(int i=1;i<(1<<(n+1));i++)
       {
           i=i|1;
           for(int j=0;j<=n;j++)
           {   // 可以 这个状态可以 到达 j
               if(dp[i][j]!=-1)
               {
                   for(int k=0;k<=n;k++)
                   {
                       if(j!=k&&(dp[i|(1<<k)][k]==-1||(dp[i|(1<<k)][k]>dp[i][j]+mapp[j][k])))
                       {
                           // 这个状态 到达 k  为 状态 i 到达 j 的 最短路到达
                          dp[i|(1<<k)][k]=dp[i][j]+mapp[j][k];
                       }
                   }
               }
           }
       }
       printf("%d\n",dp[(1<<(n+1))-1][0]);
   }
    return 0;
}