换教室

Time Limit: 20 Sec Memory Limit: 512 MB

Description

img

Input

第一行四个整数n,m,v,e。n表示这个学期内的时间段的数量;m表示牛牛最多可以申请更换多少节课程的教室;

v表示牛牛学校里教室的数量;e表示牛牛的学校里道路的数量。

第二行n个正整数,第i(1≤i≤n)个正整数表示c,即第i个时间段牛牛被安排上课的教室;保证1≤ci≤v。

第三行n个正整数,第i(1≤i≤n)个正整数表示di,即第i个时间段另一间上同样课程的教室;保证1≤di≤v。

第四行n个实数,第i(1≤i≤n)个实数表示ki,即牛牛申请在第i个时间段更换教室获得通过的概率。保证0≤ki≤1。

接下来e行,每行三个正整数aj,bj,wj,表示有一条双向道路连接教室aj,bj,通过这条道路需要耗费的体力值是Wj;

保证通过学校里的道路,从任何一间教室出发,都能到达其他所有的教室。

保证输入的实数最多包含3位小数。

Output

输出一行,包含一个实数,四舎五入精确到小数点后恰好2位,表示答案。你的

输出必须和标准输出完全一样才算正确。

Sample Input

3 2 3 3
　2 1 2
　1 2 1
　0.8 0.2 0.5
　1 2 5
　1 3 3
　2 3 1

Sample Output

2.80

HINT

1≤aj,bj≤v, 1≤wj≤100。

1≤n≤2000, 0≤m≤2000, 1≤v≤300, 0≤e≤90000。

Main idea

给定n个 原本教室ci 和 替换教室di，可以申请m次换课，如果 i 换课了则可以在di上课，否则在ci上课，每个教室之间有距离，求期望最小距离。

Solution

很简单的期望DP，我们令 f[i][j][0\1] 表示 到了第 i 个状态，已经换了 j 次课，这次换不换课，然后分四种情况讨论一下即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>    
#include<string>    
#include<algorithm>    
#include<cstdio>    
#include<cstring>    
#include<cstdlib>
#include<cmath>
using namespace std;  

#define Road(a,b) (double)w[a][b]
#define tense(a,b) a = a<b ? a:b;

const int ONE = 2005;
const double INF = 1e18;

int n,m,v,e;
int x,y,z;
int c[ONE],d[ONE];
int w[301][301];
double f[ONE][ONE][2],k[ONE];
double Ans;

int get()
{    
    int res=1,Q=1;char c;    
    while( (c=getchar())<48 || c>57 ) 
        if(c=='-')Q=-1; 
    res=c-48;     
    while( (c=getchar())>=48 && c<=57 )    
        res=res*10+c-48;    
    return res*Q;    
}

void Floyed()
{
    for(int k=1; k<=v; k++)
        for(int i=1; i<=v; i++)
            for(int j=1; j<=v; j++)
                tense(w[i][j], w[i][k] + w[k][j]);
}

double Eap10(int i)
{
    return Road( c[i],c[i+1] ) * (1-k[i]) + Road( d[i],c[i+1] ) * k[i];
}

double Eap01(int i)
{
    return Road( c[i],c[i+1] ) * (1-k[i+1]) + Road( c[i],d[i+1] ) * k[i+1];
}

double Eap11(int i)
{
    return 
        Road( c[i], c[i+1] ) * (1-k[i]) * (1-k[i+1]) 
        + Road( c[i], d[i+1] ) * (1-k[i]) * k[i+1]
        + Road( d[i], c[i+1] ) * k[i] * (1-k[i+1])
        + Road( d[i], d[i+1] ) * k[i] * k[i+1]; 
}

void DisApply(int i,int j)
{ 
    if(j>=0) f[i+1][j][0] = tense(f[i+1][j][0], f[i][j][0] + Road( c[i],c[i+1] ) );
    if(j>=1) f[i+1][j][0] = tense(f[i+1][j][0], f[i][j][1] + Eap10(i) );
}

void Apply(int i,int j)
{
    if(j>=1) f[i+1][j][1] = tense(f[i+1][j][1], f[i][j-1][0] + Eap01(i) );
    if(j>=2) f[i+1][j][1] = tense(f[i+1][j][1], f[i][j-1][1] + Eap11(i) );
}

int main()  
{    
    n = get();  m = get();  v = get();  e = get();
    for(int i=1; i<=n; i++) c[i] = get();
    for(int i=1; i<=n; i++) d[i] = get();
    for(int i=1; i<=n; i++) scanf("%lf", &k[i]);

    memset(w, 1, sizeof(w));
    for(int i=1; i<=v; i++) w[i][i] = 0;
    for(int i=1; i<=e; i++)
    {
        x = get();  y = get();  z = get();
        w[x][y] = min(w[x][y], z);
        w[y][x] = min(w[y][x], z);
    }
    Floyed();

    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=1; i<=n-1; i++)
        for(int j=0; j<=m; j++)
            DisApply(i,j), Apply(i,j);

    Ans = INF;
    for(int j=0; j<=m; j++)
    {
        tense(Ans, f[n][j][0]);
        tense(Ans, f[n][j][1]);
    }

    printf("%.2lf",Ans);
}