记录编号	444299	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016]换教室	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	1.057 s
提交时间	2017-09-02 16:16:45	内存使用	77.05 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn=2000+5;
const double eps=4*1e-4;
vector<pair<int ,int > > g[maxn];
#define MP make_pair
void addedge(int from,int to,int cost)
{
    g[from].push_back(MP(cost,to));
    g[to].push_back(MP(cost,from));
}
int n,m,v,e;
double K[maxn];
double dp[maxn][maxn][2];
int c[maxn],d[maxn];
const int inf=0x3f3f3f3f;
int dis[maxn][maxn];
int getcost(int u,int v){return u==0?0:dis[u][v];}
int main()
{
    //#ifdef ONLINE_JUDGE
    freopen("classrooma.in","r",stdin);
    freopen("classrooma.out","w",stdout);
    //#endif
    //freopen("1.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=n;++i) scanf("%d",&c[i]);
    for(int i=1;i<=n;++i) scanf("%d",&d[i]);
    for(int i=1;i<=n;i++) scanf("%lf",&K[i]);
    memset(dis,inf,sizeof(dis));
    for(int i=0;i<e;i++) {
        int from,to,cost;
        scanf("%d%d%d",&from,&to,&cost);
        if(from==to) continue;
        int realcost=cost;
        realcost=min(dis[from][to],realcost);//add this line 4->16 points
        dis[from][to]=dis[to][from]=realcost;
    }
    for(int i=1;i<=v;i++) dis[i][i]=0;
    for(int k=1;k<=v;k++)
        for(int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    /*for(int i=1;i<=v;i++){
        for(int j=1;j<=v;j++){
            printf("%d ",dis[i][j]);
        }puts("");
    }puts("");*/
    for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j][0]=dp[i][j][1]=1e60;
    dp[0][0][0]=0;
    dp[1][1][0]=0,dp[1][1][1]=0,dp[1][0][0]=0;//add this line->16->44 points
    //printf("%lf\n",dp[2][2][0]);
    for(int i=2;i<=n;i++){
        for(int j=0;j<=min(m,i);j++){
            if(j>=1) dp[i][j][1]=min(dp[i-1][j-1][0]+(double)getcost(c[i-1],d[i])*K[i]
                                    +(double)getcost(c[i-1],c[i])*(1.0-K[i]),
    dp[i-1][j-1][1]+K[i-1]*((double)getcost(d[i-1],d[i])*K[i]+(double)getcost(d[i-1],c[i])*(1.0-K[i]))
                +(1-K[i-1])*((double)getcost(c[i-1],d[i])*K[i]+(double)getcost(c[i-1],c[i])*(1.0-K[i])));
            dp[i][j][0]=min(dp[i-1][j][0]+(double)getcost(c[i-1],c[i]),
                        dp[i-1][j][1]+(double)getcost(d[i-1],c[i])*K[i-1]+(double)getcost(c[i-1],c[i])*(1.0-K[i-1]));
        }
    }
    /*for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            printf("dp[%d][%d][0]=%lf dp[%d][%d][1]=%lf\n",i,j,dp[i][j][0],i,j,dp[i][j][1]);
        }puts("");
    }puts("");*/
    double Ans=1e60;
    for(int i=0;i<=m;i++) Ans=min(Ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2lf\n",Ans);
    return 0;
}