在一个无向图中..从某点出发..每个边正好经过一次可以回到自己..必要条件是所有点的度为偶数..也就在一个无向图中存在欧拉回路的必要条件...注意..是必要条件...比如说...图是不连通的...
对应本题....题目是说从点1出发边可以经过任意多次..遍历完所有的边..回到点1的最短距离..一看N<=15...状态压缩DP..但怎么设置状态呢？...看一种特殊的情况..若是点1可以到达所有点..并且所有点的度为偶数..问题不就和欧拉回路相同么...所有边长度之和就是答案..但是题目中有度为奇数的点..就不得不多走一些路...让有些边经过不止一次..这些多走的边可以看成多加的边..比如样例2..3走回1..可以看做3到1加了一条长度为7的边...
问题转换..最短要加多长的若干边..使得这个无向图成为一个满足欧拉回路的图...
先用floyd找出任意两点的最短路径...作为加边的预处理...然后枚举所有的奇数度点...看怎么加边方案最优...枚举这个感觉太麻烦..不如用状态dp来做这个过程...状态k代表其为1的点度都是偶的需要加最短长度的边...由于要加边必定是加在两个度为奇的点上...所以对于一个状态..枚举其为0代表的两个奇数度点..进行更新..
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 16
using namespace std;
int n,sum,dp[1<<MAXN],arc[MAXN][MAXN],d[MAXN];
void Floyd()
{
int k,i,j;
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
arc[i][j]=min(arc[i][j],arc[i][k]+arc[k][j]);
}
int getans()
{
int i,j,x,t,totol;
Floyd();
for (i=1;i<n;i++)
if (d[i] && arc[0][i]>oo) return -1;
memset(dp,0x7f,sizeof(dp));
dp[0]=0;
totol=(1<<n)-1;
for (t=0;t<=totol;t++)
{
for (i=0;i<n;i++)
if (d[i]%2 && (t & (1<<i))) break;
if (i==n) dp[t]=0; //该状态不含奇数度点
for (i=0;i<n;i++)
if (d[i]%2 && !(t & (1<<i))) // 枚举奇数度点i
for (j=i+1;j<n;j++)
if (d[j]%2 && !(t & (1<<j)) && arc[i][j]<oo) // 枚举奇数度点j
dp[t|(1<<i)|(1<<j)]=min(dp[t|(1<<i)|(1<<j)],dp[t]+arc[i][j]);
}
if (dp[totol]>oo) return -1;
return sum+dp[totol];
}
int main()
{
int m;
while (~scanf("%d%d",&n,&m))
{
sum=0;
memset(arc,0x3f,sizeof(arc));
memset(d,0,sizeof(d));
for (int i=1;i<=m;i++)
{
int x,y,l;
scanf("%d%d%d",&x,&y,&l);
sum+=l;
x--,y--;
arc[y][x]=arc[x][y]=min(arc[x][y],l);
d[x]++,d[y]++;
}
printf("%d\n",getans());
}
return 0;
}