题目中说明每个城市至少要走一次，至多走2次，因此要用到三进制压缩，然后就是状态转移方程了。
这道题就处理三进制的地方麻烦一点。同时注意，在选择最小长度时，一定是要每一个点都经过至少一次的，即是状态的每一个三进制位均 >=1.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int inf=1<<30;
struct Edge{int u,v,c;int next;
}edge[2000];
int tot,n,m;
int head[15];
int dp[60000][11],tir[60000][12],s[12];struct Status{int i,j,c;Status(){}Status(int ii,int jj,int cc){i=ii,j=jj,c=cc;}
}que[1800000];
int hed,tail;void addedge(int u,int v,int c){edge[tot].u=u;edge[tot].v=v;edge[tot].c=c;edge[tot].next=head[u];head[u]=tot++;
}void init() { s[0]=1; for(int i=1; i<=10; i++) s[i]=s[i-1]*3; for(int i=0; i<=s[10]; i++){ int t=i; for(int j=0; j<10; j++){ tir[i][j]=t%3; t/=3; } }
}void slove(){int u,v;int ans=inf;while(hed<tail){Status tmp=que[hed++];if(dp[tmp.i][tmp.j]<tmp.c) continue;bool flag=true;for(int i=0;i<n;i++){if(tir[tmp.i][i]==0) {flag=false; break ;}}if(flag) ans=min(ans,dp[tmp.i][tmp.j]);u=tmp.j;for(int e=head[tmp.j];e!=-1;e=edge[e].next){v=edge[e].v;if(v==u||tir[tmp.i][v]==2) continue;int states=tmp.i+s[v];if(dp[states][v]>tmp.c+edge[e].c){dp[states][v]=tmp.c+edge[e].c;que[tail++]=Status(states,v,dp[states][v]);}}}printf("%d\n",ans==inf?-1:ans);
}int main(){int u,v,c;init();while(scanf("%d%d",&n,&m)!=EOF){memset(head,-1,sizeof(head));tot=0;for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&c);u--; v--;addedge(u,v,c);addedge(v,u,c);}for(int i=0;i<s[n];i++){for(int j=0;j<n;j++)dp[i][j]=inf;}hed=tail=0;for(int i=0;i<n;i++){int st=s[i];dp[st][i]=0;que[tail++]=Status(st,i,0);}slove();}return 0;
}
