先弗洛伊德,然后把状态拆分遗传
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define f(a,b,c) g[a+10][b+10][c+1]
#define N 2100
#define M 320
using namespace std;
typedef double D;
int d[M][M],c[N][];
D g[N][N][];
int n,m,v,e;
D w[N];
inline int MIN(int x,int y)
{
return x<y?x:y;
}
inline D Min(D x,D y)
{
return x<y?x:y;
}
int main()
{
freopen("classrooma.in","r",stdin);
freopen("classrooma.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=;i<=n;i++)
scanf("%d",&c[i][]);
for(int i=;i<=n;i++)
scanf("%d",&c[i][]);
for(int i=;i<=n;i++)
scanf("%lf",&w[i]);
memset(d,0x3f,sizeof(d));
for(int i=;i<=v;i++)
d[i][i]=;
for(int i=;i<=e;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
d[y][x]=d[x][y]=MIN(d[x][y],z);
}
for(int k=;k<=v;k++)
for(int i=;i<=v;i++)
for(int j=;j<=v;j++)
d[i][j]=MIN(d[i][j],d[i][k]+d[k][j]);
for(int i=;i<N;i++)
for(int j=;j<N;j++)
for(int k=;k<;k++)
g[i][j][k]=2000000000.00;
f(,,)=;
if(m)f(,,)=;
for(int i=;i<=n;i++)
{
f(i,,)=f(i-,,)+d[c[i-][]][c[i][]];
for(int j=;j<=m;j++)
{
f(i,j,)=Min(f(i-,j,)+d[c[i-][]][c[i][]],f(i-,j,)+w[i-]*d[c[i-][]][c[i][]]+(1.0-w[i-])*d[c[i-][]][c[i][]]);
f(i,j,)=f(i-,j-,)+w[i]*w[i-]*d[c[i-][]][c[i][]]+(1.0-w[i])*w[i-]*d[c[i-][]][c[i][]]+(1.0-w[i])*(1.0-w[i-])*d[c[i-][]][c[i][]]+w[i]*(1.0-w[i-])*d[c[i-][]][c[i][]];
f(i,j,)=Min(f(i,j,),f(i-,j-,)+w[i]*d[c[i-][]][c[i][]]+(1.0-w[i])*d[c[i-][]][c[i][]]);
}
}
D ans=2000000000.00;
for(int i=;i<=m;i++)
ans=Min(ans,Min(f(n,i,),f(n,i,)));
printf("%.2lf",ans);
return ;
}