本来是在搜索专题里看到的这道题，搜索没写过去，评论区看到有人说是三进制状压，就搜索相关资料学习了一下。

HDU - 3001 Travelling

---

N进制状态压缩

关于二进制的状压，可以用移位符轻松解决，具体说明可以参考《挑战》P156，除二进制以外的进制压缩需要通过以下方法实现：

• （从第0种数起）只含单个第x种元素的n进制压缩状态可以表示为n^x。
• （从第0种数起）n种元素的所有状态总数为init[n+1]-1。
• 两种状态相加得出的状态，为两个集合的并集。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int maze[12][12];
int dp[12][60000];
int init[12];
int cnt[12];
int trans(int cnt[],int num)
{int res=0;for(int i=0;i<n;i++){cnt[i]=num%3;num/=3;if(cnt[i])res++;}return res;
}
int main()
{init[0]=1;for(int i=1;i<12;i++)init[i]=init[i-1]*3;while(cin>>n>>m){int ans=-1;memset(maze,-1,sizeof(maze));memset(dp,-1,sizeof(dp));int a,b,c;for(int i=0;i<m;i++){cin>>a>>b>>c;a--;b--;if(maze[a][b]==-1)maze[a][b]=maze[b][a]=c;elsemaze[a][b]=maze[b][a]=min(c,maze[a][b]);}for(int state=1;state<init[n];state++){int vis=trans(cnt,state);for(int i=0;i<n;i++)if(cnt[i]){if(vis==1)dp[i][state]=0;if(dp[i][state]==-1)continue;if(vis==n){if(ans==-1)ans=dp[i][state];elseans=min(ans,dp[i][state]);}for(int j=0;j<n;j++)if(i!=j&&cnt[j]!=2&&maze[i][j]!=-1){int nextstate=state+init[j];if(dp[j][nextstate]==-1)dp[j][nextstate]=dp[i][state]+maze[i][j];elsedp[j][nextstate]=min(dp[i][state]+maze[i][j],dp[j][nextstate]);}}}cout<<ans<<endl;}
}