题目大意：
中国邮递员问题。
给你一个无向带权连通图，求经过所有边并返回起点的最短路径。
思路：
Edmonds-Johnson算法。
显然，当原图为欧拉图时，答案即为其欧拉回路的长度。
考虑原图不存在欧拉回路时的情况。
一个图存在欧拉回路，当且仅当这个图中度为奇数的点的个数为0。
然而现在我们的图并不一定是欧拉图，这就说明图中有可能由度数为奇数的点。
显然，我们需要重复走的边，一定是连接这些度为奇数的点的。
我们可以用Dijkstra对这些点求最短路（由于数据范围较小，用Floyd也没关系）。
然后对所有点对之间的最短路构建新图。
再对新图跑一般图最小权完美匹配（用状压DP或者记忆化搜索）。
最后匹配出来的匹配就是重复走的路径长度。
用老图的边权和加上新图的匹配就是答案。
本来能1A的，但是由于用了平板电视，在POJ上CE了，但是在UVa上就直接0ms0kB过。
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<functional>
#include<ext/pb_ds/priority_queue.hpp>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
const int inf=0x7fffffff;
const int V=;
struct Edge {
int to,w;
};
std::vector<Edge> e[V];
void add_edge(const int &u,const int &v,const int &w) {
e[u].push_back((Edge){v,w});
e[v].push_back((Edge){u,w});
}
int deg[V];
std::vector<int> kv;
struct Vertex {
int d,id;
bool operator > (const Vertex &another) const {
return d>another.d;
}
};
int n;
int k[V][V];
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> > q;
__gnu_pbds::priority_queue<Vertex,std::greater<Vertex> >::point_iterator p[V];
inline void Dijkstra(const int &s) {
int *d=k[s];
q.clear();
for(register int i=;i<=n;i++) {
if(i!=s) {
p[i]=q.push((Vertex){d[i]=inf,i});
} else {
p[i]=q.push((Vertex){d[i]=,i});
}
}
while(q.top().d!=inf) {
const int x=q.top().id;
for(register unsigned i=;i<e[x].size();i++) {
const int &y=e[x][i].to;
if(d[x]+e[x][i].w<d[y]) {
d[y]=d[x]+e[x][i].w;
q.modify(p[y],(Vertex){d[y],y});
}
}
q.modify(p[x],(Vertex){inf,x});
}
}
int f[<<];
inline void init() {
for(register int i=;i<V;i++) {
e[i].clear();
}
kv.clear();
memset(deg,,sizeof deg);
memset(f,-,sizeof f);
}
int dfs(const int st) {
if(!st) return ;
if(~f[st]) return f[st];
f[st]=inf;
for(int i=;i<=n;i++) {
if(!(st&(<<i))) continue;
for(int j=;j<=n;j++) {
if(i==j) continue;
if(!(st&(<<j))) continue;
f[st]=std::min(f[st],dfs(st^(<<i)^(<<j))+k[i][j]);
}
}
return f[st];
}
int main() {
for(;;) {
n=getint();
if(!n) return ;
init();
int m=getint();
int ans=;
for(register int i=;i<m;i++) {
const int &u=getint(),&v=getint(),&w=getint();
deg[u]++,deg[v]++;
add_edge(u,v,w);
ans+=w;
}
int st=;
for(register int i=;i<=n;i++) {
if(deg[i]&) {
kv.push_back(i);
st|=<<i;
}
}
for(register unsigned i=;i<kv.size();i++) {
Dijkstra(kv[i]);
}
ans+=dfs(st);
printf("%d\n",ans);
}
}