[NOIP 16 향상 팀] 교실 바 꿔.

[제목 링크]
          클릭 하여 링크 열기
 【 알고리즘 】
          확률 DP
          먼저 플 로 이 드 를 한 번 달 려 서 각 교실 간 의 가장 짧 은 경 로 를 구하 고 배열 dist [] [] 에 존재 하 며 시간 복잡 도 O (V ^ 3)
          디자인 상태, f [i] [j] [k] 는 현재 i 번 째 교실 을 선 택 했 고 j 개의 교실 을 선 택 했 습 니 다. 현재 이 교실 은 선택 하지 않 습 니 다 (0. 1)
          그렇다면 상태 전이 방정식 은 무엇 일 까?
          현재 i 번 째 교실 을 선택 하고 j 개의 교실 을 선택 했다 고 가정 하면 이 교실 을 선택 하지 않 으 면 상태 이동 방정식 은
          f[i][j][0] = max{f[i-1][j][0]+dist[c[i-1]][c[i]],f[i-1][j][1]+dist[c[i-1]][c[i]]*(1-k[i-1])+dist[d[i-1]][c[i]]*k[i-1]}
      이 교실 을 선택 하면 상태 이동 방정식 은?
      f[i][j][1] = min{f[i-1][j-1][0]+dist[c[i-1]][d[i]]*k[i]+dist[c[i-1]][c[i]]*(1-k[i],f[i-1][j-1][1]+dist[d[i-1]][d[i]]*k[i-1]*k[i]+dist[c[i-1]][d[i]]*(1-k[i-1])*k[i]+dist[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+dist[d[i-1]][c[i]]*k[i-1]*(1-k[i])}
 
      그래서 이 문 제 는 쉽게 풀 렸 다!
      【 코드 】
   

#include
using namespace std;
#define MAXN 2000
#define MAXV 300

int i,j,k,n,m,v,e,a,b,w;
int dist[MAXV+10][MAXV+10],c[MAXN+10],d[MAXN+10];
double P[MAXN+10],dp[MAXN+10][MAXN+10][2];
double ans = 2e9;

template  inline void read(T &x) {
		int f=1; x=0;
		char c = getchar(); 
		for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
		for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
		x *= f;
}

template  inline void write(T x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) write(x/10);
    putchar(x%10+'0');	
}

template  inline void writeln(T x) {
    write(x);
    puts("");	
}

int main() {
		
		read(n); read(m); read(v); read(e);
		for (i = 1; i <= v; i++) {
				for (j = 1; j <= v; j++) {
						if (i != j)
								dist[i][j] = 2e9;
				}
		}
 		for (i = 1; i <= n; i++) read(c[i]);
		for (i = 1; i <= n; i++) read(d[i]);
		for (i = 1; i <= n; i++) cin >> P[i];
		for (i = 1; i <= e; i++) {
				read(a); read(b); read(w);
				dist[a][b] = min(dist[a][b],w);
				dist[b][a] = min(dist[b][a],w);	
		}
	
		for (k = 1; k <= v; k++) {
				for (i = 1; i <= v; i++) {
						if (i == k) continue;
						if (dist[i][k] == 2e9) continue;
						for (j = 1; j <= v; j++) {
								if (dist[k][j] == 2e9) continue;
								if ((i == j) || (k == j)) continue;
								dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
						}
				}
		}	
		
		for (i = 1; i <= n; i++) {
				for (j = 0; j <= m; j++) {
						dp[i][j][0] = dp[i][j][1] = 2e9;
				}	
		}
		
		dp[1][0][0] = 0; dp[1][1][1] = 0;
		for (i = 2; i <= n; i++) {
				dp[i][0][0] = dp[i-1][0][0] + dist[c[i-1]][c[i]];
				for (j = 1; j <= min(i,m); j++) {
						dp[i][j][0] = min(dp[i-1][j][0]+dist[c[i-1]][c[i]],dp[i-1][j][1]+dist[c[i-1]][c[i]]*(1.0-P[i-1])+dist[d[i-1]][c[i]]*P[i-1]);
						dp[i][j][1] = min(dp[i-1][j-1][0]+dist[c[i-1]][d[i]]*P[i]*1.0+dist[c[i-1]][c[i]]*(1.0-P[i]),
															dp[i-1][j-1][1]+
															dist[d[i-1]][d[i]]*P[i-1]*P[i]*1.0+ 
															dist[c[i-1]][d[i]]*(1.0-P[i-1])*P[i]+ 
															dist[c[i-1]][c[i]]*(1.0-P[i-1])*(1.0-P[i])+ 
														        dist[d[i-1]][c[i]]*P[i-1]*(1-P[i])*1.0); 
				}	
		}
		
		for (i = 0; i <= m; i++) ans = min(ans,min(dp[n][i][0],dp[n][i][1]));
		cout<< fixed << setprecision(2) << ans << endl;
		
		return 0;
	
}