```cpp
# include <cstdio>
# include <iostream>
# include <cstring>
using namespace std;
# define WQD 0x7f7f7f7f
# define N 305
# define M 2005
int f[N][N];
int c[M],d[M];
double k[M];
double minn;
double zyk;
double dfs(int x,double cha,int ans,int gg,int zz);
int p,q,n,m;
int main()
{
scanf("%d%d%d%d",&p,&q,&n,&m);
memset(f,0x7f,sizeof(f));
for(int i=1;i<=n;i++){
f[i][i]=0;
}
for(int i=1;i<=p;i++){
scanf("%d",&c[i]);
}
for(int i=1;i<=p;i++){
scanf("%d",&d[i]);
}
for(int i=1;i<=p;i++){
scanf("%lf",&k[i]);
}
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
if(f[u][v]<WQD&&f[u][v]>0){
f[u][v]=min(f[u][v],w);
f[v][u]=min(f[v][u],w);
}
else{
f[u][v]=w;
f[v][u]=w;
}
}
for(int h=1;h<=n;h++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(f[i][h]<WQD&&f[h][j]<WQD&&f[i][h]+f[h][j]<f[i][j]){
f[i][j]=f[i][h]+f[h][j];
}
}
}
}
zyk=min(dfs(c[1],1,0,0,1),dfs(c[1],1-k[1],0,1,1)+dfs(d[1],k[1],0,1,1));
printf("%.2lf",zyk);
return 0;
}
double dfs(int x,double cha,int ans,int gg,int zz){//分别表示这节课的教室，概率，已消耗体力值，申请了多少次,已上了多少节课；
if(zz==p){
return ans*cha;
}
if(gg>=q){
return dfs(c[zz+1],cha,ans+f[x][c[zz+1]],gg,zz+1);
}
else{
return min(dfs(c[zz+1],cha,ans+f[x][c[zz+1]],gg,zz+1),dfs(c[zz+1],cha*(1-k[zz+1]),ans+f[x][c[zz+1]],gg+1,zz+1)+dfs(d[zz+1],cha*k[zz+1],ans+f[x][d[zz+1]],gg+1,zz+1));
}
}
```
by 曾宇康 @ 2018-08-29 15:44:07
@[曾宇康](/space/show?uid=58372) 您会估计复杂度吗？搜索肯定T了啊。建议学一下动规再来做这题吧
by Marser @ 2018-08-29 15:47:19
蒟蒻不会估计复杂度 ~~但玄学剪枝应该可以~~，求教~~~~
我知道动规可做，~~但我就是想看看这样能不能做出来因为这是我第一次没看题解想出的做法~~~~
by 曾宇康 @ 2018-08-29 15:51:53
然而在旁边dalao的指点下，我知道了我没记忆化 ~~然而我不知道怎样记忆化~~，求教
by 曾宇康 @ 2018-08-29 16:02:25