状压dp-----三进制

三进制的状压dp要先预处理3^n以及每一个数的每一位

例题

hdu3001

题意：

给定n 个城市已经 m 条路 以及对应路费 c，要求遍历所有城市最少的路费，每个城市不能超过2次。

题解：

看代码吧。。

代码：

#include <bits/stdc++.h>

using namespace std;

int n,m,minn;

int load[][];

int bit[];

int dp[][];

int num[][];

#define INF 1e8

int main()

{

  freopen("noip.in","r",stdin);

  freopen("noip.out","w",stdout);

      std::ios::sync_with_stdio(false);

      bit[]=;

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

        bit[i]=bit[i-]*;

      for (int i=;i<bit[];i++)

      {

          int b=i;

          for (int j=;j<;j++)

          {

            num[i][j]=b%;

            b/=;

          }

      }

      while (cin>>n>>m)

      {

        memset(load,-,sizeof(load));

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

        {

          int a,b,c;

          cin>>a>>b>>c;

          a--;b--;

          if (load[a][b]==-)

            load[a][b]=load[b][a]=c;

          else

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

        }

        memset(dp,-,sizeof(dp));

        int flag,next;        for(int j = ; j < n; j++)

            dp[ bit[j] ][j] = ;

        minn=INF;

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

        {

          flag=;

          for (int j=;j<n;j++)

          {

             if (num[i][j]==) flag=;

             if (dp[i][j]==-) continue;

             for (int k=;k<n;k++)

             {

               if (j==k||num[i][k]==||load[k][j]==-)

                 continue;

               next=i+bit[k];

               if (dp[next][k]==-)

                 dp[next][k]=dp[i][j]+load[j][k];

              else dp[next][k]=min(dp[next][k],dp[i][j]+load[j][k]);

             }

          }

          if (flag==)

          {

            for (int j=;j<n;j++)

              if (dp[i][j]!=-)

                minn=min(minn,dp[i][j]);

          }

        }

              if(minn == INF)

            minn = -;

        printf("%d\n", minn);

      }

      return ;

}