题目传送门

分析

先用Floyd求出两点间的最短距离，包含必经边的欧拉回路，

先考虑欧拉回路的性质就是度数为偶数且连通，那如果有偶数个奇点可以两两配对。

设 \(g[S]\) 表示选择 \(S\) 中的点作为奇点时最少需要的代价，则 \(g[S|2^j|2^k]=\min\{g[i]+dis[j][k]\}\)

然后考虑怎样连起来，设 \(f[S]\) 表示状态为 \(S\) 的最小代价，三进制位的0表示没有与1连通，1表示连通且度数为奇数，2表示连通且度数为偶数。

这个状态度数并不包含必经边，直接枚举必经边的端点和连通的点转移一下，最后再将必经边的度数合起来，时间复杂度 \(O(3^nn^2)\)

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=16;
struct node{int y,w,next;}e[N*10]; queueq; int f[1600001],g[9001];
int n,m,ans=0x3f3f3f3f,dis[N][N],et=1,as[N],a[N],_2[N],_3[N],deg[N];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
void add(int x,int y,int w){
    e[++et]=(node){y,w,as[x]},as[x]=et;
	e[++et]=(node){x,w,as[y]},as[y]=et;;
}
int min(int a,int b){return a=f[y]) continue;
				if (f[y]==0x3f3f3f3f) q.push(y);
				f[y]=f[x]+dis[i+1][a[j]+1];
			}
		}
	}
}
int main(){
	n=iut(),_2[0]=_3[0]=1;
	memset(dis,0x3f,sizeof(dis));
	memset(g,0x3f,sizeof(g)),g[0]=0;
	memset(f,0x3f,sizeof(f)),f[2]=0;
	for (int i=1;i<=n;++i) _2[i]=_2[i-1]*2,_3[i]=_3[i-1]*3;
	for (int T=iut();T;--T){
		int x=iut(),y=iut(),w=iut();
		dis[x][y]=dis[y][x]=w;
		++deg[x],++deg[y],add(x,y,w);
	}
	for (int T=iut();T;--T){
		int x=iut(),y=iut(),w=iut();
		dis[x][y]=dis[y][x]=min(dis[x][y],w);
	}
	for (int k=1;k<=n;++k)
	for (int i=1;i<=n;++i)
	for (int j=1;j<=n;++j)
	    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for (int i=0;i<_2[n];++i)
	for (int j=0;j>j)&1))
	for (int k=j+1;k>k)&1))
	    g[i|_2[j]|_2[k]]=min(g[i|_2[j]|_2[k]],g[i]+dis[j+1][k+1]);
    doit();
    for (int S=0;S<_3[n];++S){
    	bool flag=0;
    	for (int i=0;i