hdu 3001 Travelling (3进制TSP)

因为每个城市允许访问两次，所以要将经典的TSP问题转化为3进制，即这个地方没访问，访问一次，两次。

状态转移是一样的，我们预处理出所有状态下每一位对应的数字。还要注意重边

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define inf 0x3f3f3f3f #define maxn 177148 using namespace std; int map[12][12]; int dp[maxn][12]; int dig[maxn][12]; int tri[12] ={1,3,9,27,81,243,729,2187,6561,19683,59049,177147}; int main() { int n,m; for(int i=0;i<177148;i++) { int t=i; for(int j=0;j<=10;j++) { dig[i][j]=t%3; t/=3; if(t==0)break; } } while(scanf("%d%d",&n,&m)!=EOF) { int ans=inf; memset(map,0x3f,sizeof map); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); if(c