题目链接：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[1<<17][17]; int mp[17][17]; int dis[17]; bool vis[1<<17][17]; 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 = 0; i < n; i++) mp[i][i] = 0; for(int i = 0; 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, 0, sizeof(vis)); dp[0][0] = 0, vis[0][0] = 1; queue<pair<int, int> > q; q.push(make_pair(0,0)); while(!q.empty()) { int s = q.front().first; int u = q.front().second; q.pop(); for(int i = 0; i < n; i++) { int ss = s | (1<<i); if(dp[ss][i] > dp[s][u] + mp[u][i]){ dp[ss][i] = dp[s][u] + mp[u][i]; if(vis[ss][i] == 0){ vis[ss][i] = 1; 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 ", i, j, dp[i][j]); printf("%d ", dp[(1<<n)-1][0]); } return 0; }