记忆化搜索血崩求助（已注释代码）（80pts）

//换教室
#include<iostream>
#include<cstdio>
#include<cstring>
#define il inline
#define rg register
#define N 2100
#define V 310
using namespace std; 

int n,m,v,e;//同题目 

int ga[N],gb[N];//两间教室 
double suc[N];//当前时间段通过的概率 

int dis[V][V];
il void Floyd(){
    //预处理最短路
    for(rg int k=1;k<=v;++k)
    for(rg int i=1;i<=v;++i)
    for(rg int j=1;j<=v;++j){
        if(dis[i][j] > dis[i][k] + dis[k][j])
        dis[i][j] = dis[i][k] + dis[k][j];
    }
    return;
}

double DP[N][N][5];//记录答案 
bool ed[N][N][5];//记录是否搜索过 
double ans;

double dp(int now,int use,int k){
	
	//now-当前时段
	//use-换教室的次数 
	//k-目前在哪一个教室 
	
    if(ed[now][use][k])return DP[now][use][k];
    ed[now][use][k]=1;
    //记忆化 
    if(now == n)return 0;
    //最后一个时段直接返回0 
    
    
    double dis1,dis2;
    if(!k){
        //没换
        dis1 = dis[ga[now]][ga[now+1]];
        dis2 = dis[ga[now]][gb[now+1]];
    }
    else{
        dis1 = dis[gb[now]][ga[now+1]];
        dis2 = dis[gb[now]][gb[now+1]];
    }
    //dis1 - 到下一个教室1的距离
	//dis2 - 到下一个教室2的距离 
    
    
    //决策：申请/不申请 
    double nowans;
    
    double to1 = dp(now+1,use,0) + dis1;//不申请
    nowans = to1;
    if(use < m){
    	//申请 
        double to2 = ( dp(now+1,use+1,0) + dis1)*(1-suc[now]) + (dp(now+1,use+1,1) + dis2)*suc[now];
        //在申请与不申请之间取min 
		nowans = min(nowans,to2);
    }
    
    return DP[now][use][k] = nowans;
}

int s1,s2,s3;

int main(){
//	freopen("class.in","r",stdin); 
    cin>>n>>m>>v>>e;
    
    //==================读入数据============ 
    for(rg int i=1;i<=n;++i){
        scanf("%d",ga+i);
    }
    for(rg int i=1;i<=n;++i){
        scanf("%d",gb+i);
    }
    for(rg int i=1;i<=n;++i){
        scanf("%lf",suc+i-1);
    }
    //=================教室1，教室2，成功概率 
    
	for(rg int i=1;i<=v;++i)
    for(rg int j=1;j<=v;++j){
    	dis[i][j]=99999999;
	}
    for(rg int i=1;i<=v;++i)
    dis[i][i]=0;
    for(rg int i=1;i<=e;++i){
        scanf("%d%d%d",&s1,&s2,&s3);
        dis[s1][s2]=dis[s2][s1]=min(dis[s1][s2],s3);
    }
    Floyd();//求dis 
    //=================Floyd 预处理路径长 
    
    ans = dp(1,0,0);
    if(m)
    ans = min(ans,dp(1,1,0)*(1-suc[0]) + dp(1,1,1)*suc[0]);
    //处理第一次是否更换教室 
    
    printf("%.2lf\n",ans);
    return 0;
}