【题目分析】
赤裸裸的状压DP。
每个点可以经过两次，问经过所有点的最短路径。
然后写了一发四进制（真是好写）
然后就MLE了。
懒得写hash了。
改成三进制，顺利A掉，时间垫底。
【代码】
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define inf 0x3f3f3f3f
int _pow[12],n,m;
int dp[100005][11],map[11][11];
int _min(int a,int b)
{return a<b?a:b;}
int main()
{
_pow[0]=1; F(i,1,11) _pow[i]=_pow[i-1]*3;
while (scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0x3f,sizeof dp);
memset(map,0x3f,sizeof map);
F(i,1,m)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);a--; b--;
map[a][b]=map[b][a]=_min(map[a][b],c);
}
F(i,0,n-1) dp[_pow[i]][i]=0;
F(i,0,_pow[n]-1)
{
F(j,0,n-1)
F(k,0,n-1)
if ((i%_pow[k+1])/_pow[k]<2)
dp[i+_pow[k]][k]=_min(dp[i+_pow[k]][k],dp[i][j]+map[j][k]);
}
int ans=inf;
F(i,0,_pow[n]-1)
{
int flag=1;
F(j,0,n-1) if ((i%_pow[j+1])/_pow[j]) continue;
else flag=0;
if (flag) F(j,0,n-1) ans=_min(ans,dp[i][j]);
}
printf("%d
",ans==inf?-1:ans);
}
}