题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5418
题目大意：有n个结点m条边（有边权）组成的一张连通图（n <16, m<100000）。求从第一个点出发，经过每个点至少一次后回到原点的最小路径边权和。
分析：发现我还真是菜。
n<16，很明显的状态压缩标记，先将所有点的编号减去1，使其从0开始编号。dp[i][j]表示从0号点出发，当前状态为i (二进制位为1表示对应点已走过，否则没走过)， 当前位置为 j， 回到原点的最小代价， 则dp[(1<<n)-1][0]为所求解，用类似 spfa 的方法可以更新到所有情况。
参考代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; int dp[<<][];
int mp[][];
int dis[];
bool vis[<<][];
int n; int main()
{
int T, m;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n, &m);
memset(mp, 0x7f, sizeof(mp));
for(int i = ; i < n; i++) mp[i][i] = ;
for(int i = ; i < m; i++) {
int u, v, d;
scanf("%d %d %d", &u, &v, &d);
u--; v--;
mp[u][v] = mp[v][u] = min(mp[u][v], d);
}
memset(dp, 0x7f, sizeof(dp));
memset(vis, , sizeof(vis));
dp[][] = , vis[][] = ;
queue<pair<int, int> > q;
q.push(make_pair(,));
while(!q.empty())
{
int s = q.front().first;
int u = q.front().second;
q.pop();
for(int i = ; i < n; i++)
{
int ss = s | (<<i);
if(dp[ss][i] > dp[s][u] + mp[u][i]){
dp[ss][i] = dp[s][u] + mp[u][i];
if(vis[ss][i] == ){
vis[ss][i] = ;
q.push(make_pair(ss, i));
}
}
}
}
//for(int i = 0; i < (1<<n); i++) for(int j = 0; j < n; j++) printf("%d %d: %d\n", i, j, dp[i][j]);
printf("%d\n", dp[(<<n)-][]);
}
return ;
}