求从1点出发，走遍所有的点，然后回到1点的最小代价。
每个点可以走若干遍。
如果每个点只能走一遍，那么设dp[i][s]为走完s状态个点（s是状态压缩），现在位于i的最小花费。
然后枚举从哪个点回到原点即可。
但是现在每个点不止走一次，那么状态就不好表示了，但是，我们可以用floyd处理出任意两点的最短距离。
这样子，可以用上面的方式求解了。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef __int64 LL;
const int INF = ;
/* */
int dp[][];
int dist[][];
int g[][];
void input(int &x)
{
char ch = getchar();
while (ch<'' || ch>'')ch = getchar();
x = ;
while (ch >= ''&&ch <= '')
{
x = x * + ch - '';
ch = getchar();
}
}
int ans; int main()
{
//freopen("d:/1.in", "r", stdin);
int t, n, m, u, v,dis;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
{
g[i][j] = INF;
}
for (int i = ; i < m; ++i)
{
input(u);
input(v);
input(dis);
u--;
v--;
if (g[u][v]>dis)
g[u][v] = g[v][u] = dis;
}
for (int k = ; k < n; ++k)
{
for (int i = ; i < n;++i)
for (int j = ; j < n; ++j)
g[i][j] = min(g[i][j],g[i][k]+ g[k][j]);
} for (int i = ; i <= n; ++i)
for (int s = ; s < ( << n); ++s)
dp[i][s] = INF;
dp[][] = ;
for (int s = ; s < ( << n); ++s)
{
for (int i = ; i < n; ++i)
{
if (s&( << i))
{
for (int j = ; j < n; ++j)
{
if (!(s&( << j)))
{
dp[j][s | ( << j)] = min(dp[j][s | ( << j)], dp[i][s] + g[i][j]);
}
}
}
}
}
if (n == )
{
printf("%d\n", );
continue;
}
int ans = INF;
for (int i = ; i < n; ++i)
{
ans = min(dp[i][( << n) - ] + g[i][], ans);
}
printf("%d\n", ans);
}
return ;
}