题目描述
你承包了一片香子兰花田。现在到了收获的季节，你需要把种下的香子兰全部收获起来，到花店卖掉并取得新的种子，再向田里播种下一季的香子兰。
你的花田一共由n-2片花田组成，编号从1到n-2。算上你的家和花店，一共有n个地点，其中你的家编号为0，花店编号为n-1。即，家、花田、花店都属于地点，且它们都有一个唯一的0~n-1的编号。有m条双向道路连接这些地点。保证所有地点间都是直接或间接连通的。
你需要从家里出发，经过所有的花田进行收获，再到达花店，再从花店出发经过所有花田进行播种，最后重新回到家中。当你经过一片花田的时候，你可以选择收获、播种或者什么事都不做，也就是说你经过一片未收割的花田时可以不立即收割它，播种亦然。然而，播种必须发生在你完成了所有收获并到花店交货之后。在完成最后一个花田的收获后，你必须在到达花店后才能开始播种。也就是说，在你没有收获完所有花田并到花店交货前，即使你已经经过了花店，你也不能进行播种。（啰嗦了这么多但愿讲明白了）
然而还有一个问题。在收割完花朵后，花田会变得光秃秃的，此时土地里的水分会迅速蒸发。考虑到这个问题，更早被收割的花田也理应更早地被播种。具体来说，你必须保证前一半个被收割的花田也是前一半个被播种的，向下取整。你不需要保证这些花田收割和播种的顺序完全一致，而只需要保证前一半名的集合不变即可。
现在，你需要求出完成上述一系列动作走过的最短路程。

输入格式
第一行包含两个整数n, m，表示地点总数和道路条数；
接下来m行，每行包含3个整数xi, yi, zi，表示有一条连接编号为xi和yi 的地点，长为zi的道路。

输出格式
一行，包含一个整数，表示最短路程。

样例输入

4 4
0 1 1
1 2 2
2 3 1
1 3 1

样例输出

10

样例解释
从0出发，先走到1收获（距离1），再走到2收获（距离2），再走到3交货（距离1），再走到1播种（距离1），再走到2播种（距离2），再走到1什么都不干（距离2），再走到0（距离1）。总距离为10。前一半个被收获和播种的花田集合是{1号花田}。

数据范围
对于30%的数据，有n≤8；
另有10%的数据，有m=n-1，且对1≤i≤m，保证xi=i-1，yi=i；
另有20%的数据，有m=n-1，且每个花田至多只与另外两个花田有道路相连；
对于100%的数据，有n≤20，m≤400，0≤xi, yi≤n-1，xi≠yi，0≤zi≤10000。

std

#include <cstdio>
#define inf 1000000007
#define N 24
int a[N][N],d[N][N],f[2][N][1050000],e[N],cnt[1050000],n,n1,n2,x,y,z,i,j,m,k,q,ans,sta;
int main()
{
    freopen("vanilla.in", "r", stdin);
    freopen("vanilla.out", "w", stdout);
    e[0]=1;
    //预处理2^i
    for(i=1;i<=22;++i)
        e[i]=e[i-1]<<1;
    //预处理每个二进制数中有几个1
    for(i=0;i<e[20];++i)
        for(x=i;x!=0;x>>=1)
            cnt[i]+=x&1;

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
        d[i][j]=inf*(i!=j);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        ++x,++y;
        if(z<d[x][y]) 
            d[x][y]=d[y][x]=z;
    }
    // floyd求两两最短路
    for(k=1;k<=n;++k)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                if(d[i][k]+d[k][j]<d[i][j])
                    d[i][j]=d[i][k]+d[k][j];
    if(n==3)
    {
        printf("%d\n",(d[1][2]+d[2][3])*2);
        return 0;
    }
    n1=(n-2)/2;
    n2=n-2-n1;
    //求从家、花店开始，走到点i，经过的点为j的最短路
    //q=0：从家开始，q=1：从花店开始
    for(q=0;q<=1;++q)
    {
        //初始化状态
        for(i=1;i<=n;++i)
        for(j=0;j<e[n-2];++j)
            f[q][i][j]=inf;
        if(q==0)
        {
            for(i=2;i<n;++i)
                f[q][i][e[i-2]]=d[1][i];
        }
        else
        {
            for(i=2;i<n;++i)
                f[q][i][e[i-2]]=d[n][i];
        }
        //dp
        for(j=1;j<e[n-2];++j)
            if(cnt[j]<n2)
        for(i=2;i<n;++i)
            if(f[q][i][j]<inf)
        for(k=2;k<n;++k)
            if(f[q][i][j]+d[i][k]<f[q][k][j|e[k-2]])
                f[q][k][j|e[k-2]]=f[q][i][j]+d[i][k];
    }
    
    ans=inf;
    //枚举先走到的一半为sta
    for(sta=0;sta<e[n-2];++sta)
    if (cnt[sta]==n1)
    {
        //前半段
        x=inf; //x记录前半段的最短距离
        //枚举前一半中最后一个收割的点是i
        for(i=2;i<n;++i)
            if (sta&e[i-2])
            //枚举后一半中第一个收割的点是j
            for(j=2; j<n; ++j)
            if(!(sta&e[j-2]))
                if(f[0][i][sta]+d[i][j]+f[1][j][e[n-2]-1-sta]<x)
                    x=f[0][i][sta]+d[i][j]+f[1][j][e[n-2]-1-sta];
        //后半段
        //枚举前一半中最后一个播种的点是i
        for(i=2;i<n;++i)
            if(sta&e[i-2])
        //枚举后一半中第一个播种的点是j
            for(j=2;j<n;++j)
            if(!(sta&e[j-2]))
                if(x+f[1][i][sta]+d[i][j]+f[0][j][e[n-2]-1-sta]<ans)
                ans=x+f[1][i][sta]+d[i][j]+f[0][j][e[n-2]-1-sta];
    }
    printf("%d\n",ans);
    return 0;
}