【算法】期望DP+floyd
【题解】用floyd预处理最短距离。
注意重边与自环——图论双毒！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
QAQ
然后搞清楚方案和概率的问题，我们DP是要决策最优方案。
f[i][j][0~1]表示前i个，剩余j份申请资格，当前第i个是否申请的最小期望（注意是是否申请，和通过无关）
然后转移就是从前面申请或不申请中选最小的转移，转移时有涉及申请的在叠加概率。
不要怕调出来过不了，怕的是没看清题意QAQ重边！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxv=;
int a[maxn][maxn],n,m,v,e,c[maxn],d[maxn];
double k[maxn],f[maxn][maxn][];
void floyd()
{
for(int k=;k<=v;k++)
for(int i=;i<=v;i++)
for(int j=;j<=v;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
double calc(int i,int j,int l,int x)
{
if(l==)return f[i][j][]+a[c[i]][x];
else return k[i]*(f[i][j][]+a[d[i]][x])+(-k[i])*(f[i][j][]+a[c[i]][x]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=;i<=n;i++)scanf("%d",&c[i]);
for(int i=;i<=n;i++)scanf("%d",&d[i]);
for(int i=;i<=n;i++)scanf("%lf",&k[i]);
memset(a,0x3f,sizeof(a));
for(int i=;i<=e;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
int z=a[u][v];
a[u][v]=a[v][u]=min(w,z);
}
for(int i=;i<=v;i++)a[i][i]=;
floyd();
for(int i=;i<=v;i++)a[][i]=a[i][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
f[i][j][]=f[i][j][]=1e9;
f[i][j][]=min(calc(i-,j,,c[i]),calc(i-,j,,c[i]));
if(j<m)f[i][j][]=min(k[i]*calc(i-,j+,,d[i])+(-k[i])*calc(i-,j+,,c[i]),k[i]*calc(i-,j+,,d[i])+(-k[i])*calc(i-,j+,,c[i]));
}
}
printf("%.2lf",min(f[n][][],f[n][][]));
return ;
}