例题连接：https://ac.nowcoder.com/acm/problem/16428

/*少说话，多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
/*这n个时间段是连续的（要不然这道题咋做呀），就是安排的上课时间是连续的*/
const int maxn = 2009;
const int maxv = 309;
int e[maxv][maxv];

int c[maxn]; //储存牛牛被安排的教室
int d[maxn]; //另一间同一时间段的上课的教室
double k[maxn]; //申请成功的概率（在0～1范围内，0和1都可以取）

double f[maxn][maxn][2];
int n, m, V, E;
int a, b, w;

void folyd()  //求出各个点之间的最短路径，储存在e二维数组里面）
{
    for (int k=1; k<=V; k++)
        for (int i=1; i<=V; i++)
            for (int j=1; j<=V; j++)
                e[i][j] = min(e[i][j], e[i][k]+e[k][j]);
}

int main()
{
    cin >> n >> m >> V >> E;    //分别表示：时间段的数量(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("%lf", &k[i]);

    memset(e, 0x3f3f3f3f, sizeof e);  //将每一个教室到比的教室的距离都初始化为最大值:65

    for (int i=1; i<=V; i++) e[i][i] = 0; //每一个教室到自己的距离都是0

    for (int i=1; i<=E; i++)
    {
        scanf("%d%d%d", &a, &b, &w);         //w的取值范围是1～100
        e[a][b] = e[b][a] = min(e[a][b], w); //更新两个教室之间的距离
    }

    folyd(); //求出各个点之间的最短路径，储存在e二维数组里面）

    for(int i=1;i<=n;i++)//手动memset，将
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=1;k++)
            {
                f[i][j][k]=0x3f3f3f3f;
            }
        }
    }
    //f的当i=1的情况，因为j<=m&&j<=i，所以j的取值就是0和1
    //当j=0的时候，就是没有一次的交换，所以后面k也不可能为1，（因为如果是1的话，代表有了交换，跟j=0没有交换矛盾），所以当j=0的时候，k只有一种情况，就是k=0
    //同理当j=1的时候，k也只有一种情况就是k=1
    //所以在定义边界条件的时候只需要定义两个f就可以了。

    //f[i][j][k]表示的是：在第i个时间段（一共n个时间段）交换了j次教室（最多可以交换m次）k代表这次交换或者不交换

    f[1][0][0] = f[1][1][1] = 0; //边界条件（具体为什么在上面有描述）

    for (int i=2; i<=n; i++) //第一维从第2开始，第一维的1已经被初始化过了
    {
        for (int j=0; j<=m&&j<=i; j++) //因为最多m次交换，所以最多交换m次，因为i代表的是几个时间段，所以肯定不能超过时间段，所以j<=i
        {
            //在第i个时间段，不申请换教室
            f[i][j][0] =  min(f[i-1][j][0] + e[c[i-1]][c[i]]  , //第i-1个时间段也不申请换教室（如果不交换教室的话，还是从c[i-1]到c[i]这条路径上课，当然走的是两者之间的最短路）
                             f[i-1][j][1]                       //第i-1个时间段申请教室
                             +  k[i-1] * e[d[i-1]][c[i]]        //上一个点申请成功，申请成功的概率是k[i-1]，并且上一个点的教室变成d[i-1]，而不是c[i-1]
                             + (1.0-k[i-1]) * e[c[i-1]][c[i]]); //上一个点申请失败，申请失败的概率是1.0-k[i-1]，上一个点的教室不变
            //在第i个时间段，申请换教室
            if (j == 0) continue;
            f[i][j][1] = min(
                             f[i-1][j-1][0] + k[i] * e[c[i-1]][d[i]] //第i-1个时间段不申请换教室，+ 第i个时间段申请成功和不成功
                             + (1.0-k[i]) * e[c[i-1]][c[i]],
                             //第i-1个时间段内申请换教室，（不成功和成功）+ 第i个时间段申请成功和不成功
                             f[i-1][j-1][1]
                             + k[i] * k[i-1] * e[d[i-1]][d[i]]    //两次交换都成功
                             + k[i] * (1.0-k[i-1]) * e[c[i-1]][d[i]] //i成功，i-1不成功
                             + (1.0-k[i]) * k[i-1] * e[d[i-1]][c[i]] //i不成功，i-1成功
                             + (1.0-k[i]) * (1.0-k[i-1]) * e[c[i-1]][c[i]]); //都不成功
        }
    }
    double ans = 9e99;
    for (int i=0; i<=m; i++)
    {
        ans = min(ans, min(f[n][i][0], f[n][i][1])); //最后肯定要到n个时间段，所以最后的遍历这里，第一维都是n，然后在从一共进行多少次交换入手，因为不一定换越多越好，每次都考虑换和不换两种情况
    }
    printf("%.2lf\n", ans);
    return 0;
}