#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const float inf=100000;
int n,m,v,e;//总时间段 可申请更换上限 教室数量 道路数量（有自环）
int c[100001],d[100001];//初始安排 另一计划
float k[100001];//更换教室成功几率
float road[10001][10001];//教室间的距离
float f[3000][3][3000];//表示 第i个阶段 选择第j种教室 换x次教室 的最小消耗
float ans=100000.00;
float smaller(float a,float b)
{
if(a<b)return a;
else return b;
}
void floyd()//求所有点对最短路径
{
for(int o=1;o<=v;o++)//中转点
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++)
road[i][j]=smaller(road[i][o]+road[o][j],road[i][j]);
}
int main()
{
freopen("换教室的测试数据.txt","r",stdin);
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
for(int i=1;i<=n;i++)scanf("%f",&k[i]);
for(int i=1;i<=v;i++)//距离初始化
{
for(int j=1;j<=v;j++)
{
if(i==j)road[i][j]=0.00;
else
road[i][j]=inf;
}
}
for(int i=1;i<=e;i++)
{
int x,y;
float z;
scanf("%d%d%f",&x,&y,&z);
road[x][y]=z;
road[y][x]=z;
}
floyd();//求任意点对最短距离（暨权值）
for(int i=2;i<=n;i++)//枚举只考虑前2到前n个阶段
for(int x=0;x<=m;x++)//从更换0次教室枚举到m次的上限
{ //枚举本次阶段的两种情况：1表示不换 2表示换
f[i][1][x]=smaller(f[i-1][1][x]+road[c[i-1]][c[i]],f[i-1][2][x]+road[d[i-1]][c[i]]);
//从本状态的不换情况考虑
if(x>=1)
f[i][2][x]=smaller(f[i-1][1][x-1]+road[c[i-1]][d[i]]*k[i]+road[c[i-1]][c[i]]*(1-k[i]),f[i-1][2][x-1]+road[d[i-1]][c[i]]*k[i]+road[d[i-1]][c[i]]*(1-k[i]));
//从本状态要换的情况考虑
}
for(int i=0;i<=m;i++)//枚举m(最终)状态下最终所换教室数
{
ans=smaller(ans,f[n][1][i]);
ans=smaller(ans,f[n][2][i]);
}
printf("%.2f",ans);
return 0;
}
保证Floyd以及之前的是对的，验证过。大神帮忙看一下。跪~跪~跪~跪~跪~跪~跪