스탠나 나무

#include<map>

#include<set>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<string>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define Maxn 210

#define Maxm 100010

#define LL __int64

#define Abs(x) ((x)>0?(x):(-x))

#define lson(x) (x<<1)

#define rson(x) (x<<1|1)

#define inf 0x3f3f3f3f

#define Mod 1000000007

using namespace std;

int dp[Maxn][1<<13],dis[Maxn][Maxn],n,m,K,ans[1<<13];

void init()

{

    memset(dp,63,sizeof(dp));

    memset(dis,63,sizeof(dis));

    memset(ans,63,sizeof(ans));

}

void floyd()

{

    int i,j,k;

    for(k=1;k<=n;k++){

        dis[k][k]=0;

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

            }

        }

    }

}

bool Ok(int s)

{

    int res=0;

    for(int i=0;s;i++,s>>=1)

        res+=(s&1)*(i<K?1:-1);

    return (res==0?true:false);

}

void solve()

{

    int i,j,k;

    int N=1<<(2*K);

    N--;

    for(i=0;i<K;i++){

        for(j=1;j<=n;j++){

            dp[j][1<<i]=dis[i+1][j];

            dp[j][1<<(K+i)]=dis[n-K+i+1][j];

        }

    }

    for(i=1;i<=N;i++){

        if((i&(i-1))==0) continue;

        for(j=1;j<=n;j++){

            dp[j][i]=inf;

            for(k=(i-1)&i;k;k=(k-1)&i){

                dp[j][i]=min(dp[j][i],dp[j][k]+dp[j][i-k]);



            }

        }

        for(j=1;j<=n;j++){

            for(k=1;k<=n;k++){

                dp[j][i]=min(dp[j][i],dp[k][i]+dis[j][k]);

            }

        }

    }

    for(i=1;i<=N;i++){

        ans[i]=inf;

        for(j=1;j<=n;j++) ans[i]=min(ans[i],dp[j][i]);

    }

    for(i=0;i<=N;i++){

        if(Ok(i)){

            for(j=(i-1)&i;j;j=(j-1)&i){

                if(Ok(j)){

                    ans[i]=min(ans[i],ans[j]+ans[i-j]);

                }

            }

        }

    }

    if(ans[N]>=inf)

        printf("No solution
");

    else

        printf("%d
",ans[N]);

}

int main()

{

    int i,j,u,v,val,t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d",&n,&m,&K);

        init();

        for(i=1;i<=m;i++){

            scanf("%d%d%d",&u,&v,&val);

            dis[u][v]=dis[v][u]=min(dis[u][v],val);

        }

        floyd();

        solve();

    }

    return 0;

}