HDU4085 Peach Blossom Spring

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
using namespace std;
typedef long long LL;
const int MAXN = 52;
const int MAXM = 2017;
const int MAXS = 1024;
int n,m,k,ecnt,f[MAXN][MAXS],S,head,tail,dui[MAXM*100];
int first[MAXN],to[MAXM],Next[MAXM],w[MAXM],g[MAXS];
bool vis[MAXN];
inline void link(int x,int y,int z){ Next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z; }
inline int calc(int s){ int tot=0; while(s) tot+=s&1,s>>=1; return tot; }
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline void SPFA(int s){
	head=tail=0; for(int i=1;i<=n;i++) if(f[i][s]!=f[0][0]) dui[++tail]=i,vis[i]=1;
	int u;
	while(head<tail) {
		head++; u=dui[head]; vis[u]=0;
		for(int i=first[u];i;i=Next[i]) {
			int v=to[i];
			if(f[v][s]>f[u][s]+w[i]) {
				f[v][s]=f[u][s]+w[i];
				if(!vis[v]) { vis[v]=1; dui[++tail]=v; }
			}
		}
	}
}

inline void work(){
	int T=getint(); int x,y,z,now;
	while(T--) {
		n=getint(); m=getint(); k=getint();
		ecnt=0; memset(first,0,sizeof(first));
		for(int i=1;i<=m;i++) {
			x=getint(); y=getint(); z=getint();
			link(x,y,z); link(y,x,z);
		}
		memset(f,0x3f,sizeof(f)); S=(1<<(k*2))-1;
		for(int i=1;i<=k;i++) f[i][(1<<(i-1))]=0;
		for(int i=n-k+1;i<=n;i++) f[i][(1<<(i+k*2-n-1))]=0;
		for(int s=1;s<=S;s++) {
			for(int i=1;i<=n;i++) {
				for(int from=(s-1)&s;from;from=(from-1)&s) {
					if(f[i][from]==f[0][0] || f[i][s-from]==f[0][0]) continue;
					now=f[i][from]+f[i][s-from];
					if(f[i][s]>now) f[i][s]=now;
				}
			}
			SPFA(s);
		}

		memset(g,0x3f,sizeof(g)); int ss=(1<<k)-1;
		//可能是森林，考虑将几棵树组合
		for(int s=1;s<=S;s++) {
			if(calc(s&ss)!=calc(s>>k)) continue;
			for(int i=1;i<=n;i++)
				g[s]=min(g[s],f[i][s]);
		}

		for(int s=1;s<=S;s++) {
			for(int from=(s-1)&s;from;from=(from-1)&s) {
				if(g[from]==g[0] || g[s-from]==g[0]) continue;
				g[s]=min(g[s],g[from]+g[s-from]);
			}
		}
		if(g[S]==g[0]) puts("No solution");
		else printf("%d\n",g[S]);
	}
}

int main()
{
    work();
    return 0;
}