题目:HDU3001
#include <bits/stdc++.h> using namespace std; int state[12],vis[60000][12],dis[12][12]; int n,m,dp[60000][12]; void init()//预处理三进制状态 { state[1]=1; for(int i=2;i<=11;i++) state[i]=state[i-1]*3;//最多10个点，要处理到11 for(int i=0;i<=state[11];i++) { int tmp=i; for(int j=1;j<=10;j++){// 把10位都处理一下 vis[i][j]=tmp%3; tmp/=3; } } } int main() { init(); while(cin>>n>>m) { memset(dp,20,sizeof(dp)); memset(dis,20,sizeof(dis)); int inf=dp[0][0]; for(int i=1;i<=n;i++) dp[state[i]][i]=0; for(int i=1;i<=m;i++) { int l,r,w; cin>>l>>r>>w; dis[l][r]=dis[r][l]=min(dis[l][r],w); } int ans=inf; for(int i=0;i<state[n+1];i++)//枚举状态 { bool flag=1; for(int j=1;j<=n;j++)//枚举状态的每一位 { if(!vis[i][j]) flag=0;//本状态没有达成目的 if(dp[i][j]==inf) continue;//没有前驱 for(int k=1;k<=n;k++)//枚举下一个节点 { if(vis[i][k]>=2) continue; if(dis[j][k]==inf) continue;//没有路 dp[i+state[k]][k]=min(dp[i+state[k]][k],dp[i][j]+dis[j][k]); } } if(flag){ for(int j=1;j<=n;j++) ans=min(ans,dp[i][j]); } } if(ans==inf) cout<<-1<<endl; else cout<<ans<<endl; } }