测试点1~3
N<=8
预处理两两之间的最短路长度
枚举按什么顺序收割、播种所有点，再求路线长度
测试点4
m=n-1，且对1≤i≤m，保证xi=i-1，yi=i
是一条直线，家和花店在两端
最优策略是先收割前半段或后半段的花田
总共往返2趟
Ans = 4*所有道路总长度-2*(家到第一个花店的距离+最后一个花田到花店的距离)
测试点5~6
m=n-1，且每个花田至多只与另外两个花田有道路相连
是一条直线，家和花店不一定在两端
最优策略依旧是先收割前半段或后半段的花田
总共往返两趟
Ans = 所有道路长度*4
如果起点在端点，ans -= 2*家到第一个花田的距离
如果终点在端点，ans -= 2*最后一个花田到花店的距离
测试点7~10
N<=20
状态压缩DP
Floyd预处理两两之间最短路，并预处理：
F[i][sta]表示从家开始，当前走到点i，已经走过sta中的点，走过的最短距离是多少
G[i][sta]表示从花店开始，当前走到点i，已经走过sta中的点，走过的最短距离是多少
枚举先收割哪些花田，记为A，其余的花田记为B
分交货前和交货后两段，单独计算最短距离。以交货前为例：
枚举A中最后一个收割的点i、B中第一个收割的点j
求min{F[i][A]+dis(i,j)+G[j][B]}
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;
//棰勫鐞?^i
for (i=1; i<=22; ++i) e[i] = e[i-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;
//姹備粠瀹躲€佽姳搴楀紑濮嬶紝璧板埌鐐筰锛岀粡杩囩殑鐐逛负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;
}

//心理AC（大家懂的）
感谢TAKAMI
#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;
}