题意：10个点，若干条边，边有花费，每个点最多走两次，求走过所有点，花费最少
分析：因为每个点最多走两次，所以联想到3进制，然后枚举状态，就行了（我也是照着网上大神的代码写的）
#include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <map> using namespace std; typedef long long LL; const int N=6e4; const int INF=0x3f3f3f3f; int bit[12]= {0,1,3,9,27,81,243,729,2187,6561,19683,59049}; int vis[N][12],dp[N][12],mp[12][12]; int main() { for(int i=1; i<59049; ++i) { int tmp=i; for(int j=1; j<=10; ++j) vis[i][j]=tmp%3,tmp/=3; } int n,m; while(~scanf("%d%d",&n,&m)) { for(int i=1; i<bit[n+1]; ++i) for(int j=1; j<=n; ++j) dp[i][j]=INF; for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) mp[i][j]=INF; for(int i=0; i<m; ++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); mp[u][v]=min(mp[u][v],w); mp[v][u]=min(mp[v][u],w); } for(int i=1; i<=n; ++i) dp[bit[i]][i]=0; int ans=INF; for(int i=1; i<bit[n+1]; ++i) { bool flag=1; for(int j=1; j<=n; ++j) { if(!vis[i][j]) { flag=0; continue; } if(dp[i][j]==INF)continue; for(int k=1; k<=n; ++k) { if(k==j)continue; if(mp[j][k]==INF||vis[i][k]>=2) continue; dp[i+bit[k]][k]=min(dp[i+bit[k]][k],dp[i][j]+mp[j][k]); } } if(flag) for(int j=1; j<=n; ++j) ans=min(ans,dp[i][j]); } if(ans==INF)printf("-1 "); else printf("%d ",ans); } return 0; }