洛谷 1850 NOIP2016提高组 换教室

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define LL long long
 5 #define rg register
 6 #define N 2010
 7 using namespace std;
 8 int n,m,v,e,dis[310][310],c[N],d[N];
 9 double f[N][N][2],k[N],ans=2e9;
10 inline int read(){
11     int k=0,f=1; char c=getchar();
12     while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
13     while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
14     return k*f;
15 } 
16 int main(){
17     n=read(); m=read(); v=read(); e=read();
18     for(rg int i=0;i<=n;i++)
19         for(rg int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=1e9;
20     f[1][0][0]=f[1][1][1]=0;
21     for(rg int i=1;i<=v;i++)
22         for(rg int j=1;j<=v;j++) if(i!=j)dis[i][j]=1e9;
23     for(rg int i=1;i<=n;i++) c[i]=read();
24     for(rg int i=1;i<=n;i++) d[i]=read();
25     for(rg int i=1;i<=n;i++) scanf("%lf",&k[i]);
26     for(rg int i=1;i<=e;i++){
27         int u=read(),v=read();
28         dis[u][v]=dis[v][u]=min(dis[u][v],read());
29     }
30     for(rg int mid=1;mid<=v;mid++)
31         for(rg int i=1;i<=v;i++)
32             for(rg int j=1;j<=v;j++) dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][mid]+dis[mid][j]);
33     for(rg int i=2;i<=n;i++){
34         int num=min(i,m);
35         for(rg int j=0;j<=num;j++){
36             f[i][j][0]=min(f[i][j][0],f[i-1][j][0]+dis[c[i-1]][c[i]]);
37             if(j>=1) 
38                 f[i][j][0]=min(f[i][j][0],f[i-1][j][1]+k[i-1]*dis[d[i-1]][c[i]]+(1-k[i-1])*dis[c[i-1]][c[i]]);
39             if(j>=1)
40                 f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]]);
41             if(j>=2){
42                 double tmp=0;
43                 tmp+=k[i-1]*k[i]*dis[d[i-1]][d[i]] + k[i-1]*(1-k[i])*dis[d[i-1]][c[i]];
44                 tmp+=(1-k[i-1])*k[i]*dis[c[i-1]][d[i]] + (1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]];
45                 f[i][j][1]=min(f[i][j][1],f[i-1][j-1][1]+tmp);
46             }
47         }
48     }
49     for(rg int i=0;i<=m;i++) ans=min(ans,min(f[n][i][0],f[n][i][1]));
50     printf("%.2lf\n",ans);
51     return 0;
52 }