[NoiPlus2016]换教室

flag++
//Writer : Hsz %WJMZBMR%tourist%hzwer

#include <iostream>

#include <cstdio>

#include <cstring>

#define LL long long

#define M(a,b) memset(a,b,sizeof a)

const int inf=0x3fffffff;

const double eps=1e-8;

int in(){

    int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}  return x*f;

}

void out(int x)

{

    int a[25],wei=0;

    if(x<0) putchar('-'),x=-x;

    for(;x;x/=10) a[++wei]=x%10;

    if(wei==0){ puts("0"); return;}

    for(int j=wei;j>=1;--j) putchar('0'+a[j]);

    putchar('\n');

}

int dis[305][305],n,m,v,e,c[2005],d[2005],head[2005],ecnt;

double p[2005],f[2005][2005][2],ans=inf;

int main()

{

    n=in(),m=in(),v=in(),e=in();

    for(int i=1;i<=n;i++)c[i]=in();

    for(int i=1;i<=n;i++)d[i]=in();

    for(int i=1;i<=n;i++)scanf("%lf",&p[i]);

    M(dis,0x3f);

    for(int i=1;i<=v;i++) dis[i][i]=0;

    for(int i=1,a,b,dd;i<=e;i++){a=in(),b=in(),dd=in();dis[a][b]=dis[b][a]=std::min(dis[a][b],dd);}

    for(int k=1;k<=v;k++)

        for(int i=1;i<=v;i++)

            for(int j=1;j<i;j++)

                if(dis[i][j]>dis[i][k]+dis[k][j]) dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j];

    for(int i=1;i<=n;i++)

        for(int j=0;j<=m;j++)

            f[i][j][0]=f[i][j][1]=inf;

    f[1][0][0]=f[1][1][1]=0;

    for(int i=2;i<=n;i++){

        int mn=std::min(i,m);

        double d1=dis[c[i-1]][c[i]],d2=dis[d[i-1]][c[i]]*p[i-1]+d1*(1-p[i-1]),

        d3=dis[c[i-1]][d[i]]*p[i]+d1*(1-p[i]),d4=d1*(1-p[i])*(1-p[i-1])+dis[c[i-1]][d[i]]*(1-p[i-1])*p[i]+

        dis[d[i-1]][c[i]]*(1-p[i])*p[i-1]+dis[d[i-1]][d[i]]*p[i-1]*p[i];

        for(int j=0;j<=mn;j++){

            f[i][j][0]=std::min(f[i-1][j][0]+d1,f[i-1][j][1]+d2);

            if(j)f[i][j][1]=std::min(f[i-1][j-1][0]+d3,f[i-1][j-1][1]+d4);

        }

    }

    for(int i=0;i<=m;i++)

    for(int j=0;j<=1;j++){

        ans=std::min(ans,f[n][i][j]);

    }

    printf("%.2lf",ans);

    return 0;

}
巴特西

[NoiPlus2016]换教室

最新文章

热门文章
