@[颜伟业_C_Asm](/space/show?uid=56917) 为啥要判断上个课程是不是申请过的啊，本蒟蒻88分，不太懂
by jklover @ 2018-08-21 10:01:28
```cpp
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<time.h>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#define ll long long
#define oo 0x7fffffff
#define MAXN 2018
#define MAXC 329
using namespace std;
inline int read()
{
int out=0,fh=1;
char cc=getchar();
while ((cc>'9'||cc<'0')&&cc!='-')
cc=getchar();
if (cc=='-')
{
fh=-1;
cc=getchar();
}
while (cc>='0'&&cc<='9')
{
out=out*10+cc-'0';
cc=getchar();
}
return out*fh;
}
double e[MAXC][MAXC];
double f[MAXN][2][MAXN];
int c[MAXN],d[MAXN];
int N,M,V,E;
double p[MAXN];
inline void Floyd()
{
for(register int i=0;i<=N+10;++i)
for(register int j=0;j<=N+10;++j)
f[i][0][j]=f[i][1][j]=-1;
for(register int i=1;i<=V;++i)
e[i][i]=0;
for(register int k=1;k<=V;++k)
for(register int i=1;i<=V;++i)
for(register int j=1;j<=V;++j)
e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
c[0]=d[0]=0;
e[0][c[1]]=e[0][d[1]]=0;
}
double dp(int i,int pre,int j)
{
if(j<0)
return oo;
if(f[i][pre][j]!=-1)
return f[i][pre][j];
double& ans=f[i][pre][j];
if(ans==-1)
ans=oo;
if(i>N)
return ans=0;
if(pre==0)
{
ans=min(ans,dp(i+1,0,j)+e[c[i-1]][c[i]]);
ans=min(ans,(1-p[i])*(dp(i+1,0,j-1)+e[c[i-1]][c[i]])+p[i]*(dp(i+1,1,j-1)+e[c[i-1]][d[i]]));
}
else
{
ans=min(ans,dp(i+1,0,j)+e[d[i-1]][c[i]]);
ans=min(ans,(1-p[i])*(dp(i+1,0,j-1)+e[d[i-1]][c[i]])+p[i]*(dp(i+1,1,j-1)+e[d[i-1]][d[i]]));
}
return ans;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
N=read(),M=read(),V=read(),E=read();
for(register int i=1;i<=N;++i)
c[i]=read();
for(register int i=1;i<=N;++i)
d[i]=read();
for(register int i=1;i<=N;++i)
scanf("%lf",&p[i]);
memset(e,0x7f,sizeof(e));
for(register int i=1;i<=E;++i)
{
int a=read(),b=read();
double w;
scanf("%lf",&w);
e[a][b]=min(e[a][b],w);
e[b][a]=min(e[b][a],w);
}
Floyd();
printf("%.2lf",dp(1,0,M));
//fclose(stdin);
//fclose(stdout);
return 0;
}
```
by jklover @ 2018-08-21 10:09:39