HDU 3001 Travelling （状压DP，3进制）

题意：

　　给出n<=10个点，有m条边的无向图。问：可以从任意点出发，至多经过同一个点2次，遍历所有点的最小费用？

思路：

　　本题就是要卡你的内存，由于至多可经过同一个点2次，所以只能用3进制来表示，3进制可以先将表打出来。在走的时候注意只能走2次，其他的和普通的TSP状压DP是一样的。注意点：重边，自环等等，老梗了。

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 #define ULL unsigned long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 int g[N][N], dp[][N], up[N], bit[N];

 int decode(int s)//将状态s解码

 {

     int cnt=;

     for(int i=; s; i++)

     {

         bit[i]=s%;

         s/=;

         if(bit[i])  cnt++;

     }

     return cnt;

 }

 int cal(int n)

 {

     memset(dp,0x3f,sizeof(dp));

     int ans=INF;

     for(int i=; i<=n; i++)    dp[up[i-]][i]=;//先将每个起点设为0，并不影响结果

     for(int s=; s<=up[n]; s++)

     {

         int cnt=decode(s);//cnt表示已经遍历的点数

         for(int i=; i<=n; i++)   //枚举中间点

         {

             if( bit[i]> )    //确保已经遍历过i点

             {

                 for(int j=; j<=n; j++)           //枚举终点

                 {

                     if( bit[j]== )    continue;   //已经走过了2次

                     bool flag=cnt==n?true:false;//为了更新答案

                     if( bit[j]==&&cnt+==n )   flag=true;

                     int &q=dp[s+up[j-]][j];

                     if( q>dp[s][i]+g[i][j] )    q=dp[s][i]+g[i][j];

                     if(flag)                    ans=min(ans, q);

                 }

             }

         }

     }

     return ans;

 }

 void init() //3进制先打表

 {

     int a=;

     up[]=;

     for(int i=; i<N; i++)

     {

         up[i]=a;

         a*=;

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     init();

     int n, m, a, b, c;

     while(~scanf("%d%d",&n,&m)) //每个点至多可走2次

     {

         memset(g,0x3f,sizeof(g));

         for(int i=; i<=n; i++) g[i][i]=;

         for(int i=; i<m; i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             g[a][b]=g[b][a]=min(g[a][b],c);

         }

         if(n==)

         {

             puts("");

             continue;

         }

         int ans=cal(n);

         printf("%d\n", ans==INF?-:ans);

     }

     return ;

 }

AC代码