题意：
带权无向图上的中国邮路问题：一名邮递员需要经过每条边至少一次，最后回到出发点，一条边多次经过权值要累加，问最小总权值是多少。（2 <= N <= 15, 1 <= M <= 1000）
解析：
每条边都要至少经过一次， 如果每条边只能经过一次，那么是不是就是一个欧拉回路的问题，但无向图的欧拉回路必须保证 每个点的度数为偶数
所以如果有某个点的度数为奇数，那就比较尴尬了。。。
因为一条边有两个端点， 所以如果有奇数点，那么奇数点的个数一定是个偶数
我们先假设在这个无向图中有两个奇点分别为s 和 t，那么根据欧拉路径 s 一定可以经过所有边一次 然后到t ， 但我们还要回去，那么是不是走t 到 s 的最短路就好了
那么最短路算法求出这个原图中是t - s的最短路 添加到原图中，是不是就是一个欧拉回路！
同理 如果奇点个数大于2 ，那么我们就建一个二分图，把这些点分别放到左边 和 右边，每两个点的边权为它们之间的最短路，求最小权匹配就好了
然后把求出来的这些匹配 添加到原图中 求欧拉回路
但这题的n比较小 用状压去枚举所有的情况 dp一下就好了
1 如果是连通图，转2，否则返回无解并结束；
2 检查中的奇点，构成图的顶点集；
3 求出中每对奇点之间的最短路径长度，作为图对应顶点间的边权；
4 对进行最小权匹配；
5 把最小权匹配里的每一条匹配边代表的路径，加入到图中得到图；
6 在中求欧拉回路，即所求的最优路线。
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
int head[maxn], d[maxn], vis[maxn], deg[maxn], dp[ << + ];
int n, m, cnt;
vector<int> odd;
int way[][];
struct node
{
int u, v, w, next;
}Node[maxn]; void add_(int u, int v, int w)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].w = w;
Node[cnt].next = head[u];
head[u] = cnt++;
} void add(int u, int v, int w)
{
add_(u, v, w);
add_(v, u, w);
} int spfa(int s, int t)
{
for(int i = ; i < maxn; i++) d[i] = INF;
queue<int> Q;
mem(vis, );
Q.push(s);
vis[s] = ;
d[s] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
vis[u] = ;
for(int i = head[u]; i != -; i = Node[i].next)
{
node e = Node[i];
if(d[e.v] > d[u] + e.w)
{
d[e.v] = d[u] + e.w;
if(!vis[e.v])
{
Q.push(e.v);
vis[e.v] = ;
}
}
}
}
// cout << s << " " << t << endl;
// cout << d[t] << endl;
return d[t];
} void init()
{
mem(head, -);
mem(way, -);
cnt = ;
} int main()
{
init();
int edge_sum = ;
int u, v, w;
cin >> n >> m;
for(int i = ; i < m; i++)
{
cin >> u >> v >> w;
add(u, v, w);
deg[u]++;
deg[v]++;
// way[u][v] = way[v][u] = w;
edge_sum += w;
}
for(int i = ; i < n; i++) if(deg[i] & ) odd.push_back(i); //n的数比较小 所以用状压dp枚举所有情况 即可
int len = odd.size();
for(int i = ; i < ( << len); i++) dp[i] = INF;
dp[] = ;
for(int mask = ; mask < ( << len); mask++)
{
int ncnt = __builtin_popcount(mask); //统计mask中有多少个1
if(ncnt & ) continue;
vector<int> bits; //bits[i]代表了mask第bits[i]位有1 同时也是odd里的第bits[i]个数的下标
for(int i = ; i < len; i++)
if(mask & ( << i)) bits.push_back(i);
// int blen = bits.size();
for(int i = ; i < ncnt - ; i++)
{
for(int j = i + ; j < ncnt; j++)
{
int sp_mask = mask ^ ( << bits[i]) ^ ( << bits[j]);
int u = odd[bits[i]], v = odd[bits[j]];
int shost_path = way[u][v] == - ? spfa(u, v) : way[u][v];
way[u][v] = way[v][u] = shost_path;
dp[mask] = min(dp[mask], dp[sp_mask] + shost_path);
}
}
} cout << edge_sum + dp[( << len) - ] << endl; return ;
}