题解：P1850 [NOIP 2016 提高组] 换教室

· · 题解

P1850 [NOIP 2016 提高组] 换教室题解

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int dis[N][N],n,m,v,e,c[N],d[N];
double dp[N][N][3],k[N];
int main(){
    memset(dis,0x3f,sizeof dis);
    cin>>n>>m>>v>>e;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j][0] = dp[i][j][1] = 1e18;
    dp[1][0][0] = 0;
    if (m >= 1) dp[1][1][1] = 0;

    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>d[i];
    for(int i=1;i<=n;i++) cin>>k[i];
    for(int i=1;i<=e;i++){
        int x,y,z;
        cin>>x>>y>>z;
        dis[x][y]=min(dis[x][y],z);
        dis[y][x]=min(dis[y][x],z);
    }
    for(int kk=1;kk<=v;kk++)
        for(int i=1;i<=v;i++)
            for(int j=1;j<=v;j++)
                dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]);
    for (register int i = 1; i <= v; i++)dis[i][i]  = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= min(i, m); j++) {
           dp[i][j][0] = min(
                dp[i-1][j][0] + dis[c[i-1]][c[i]], 
                dp[i-1][j][1] + (1 - k[i-1]) * dis[c[i-1]][c[i]] + k[i-1] * dis[d[i-1]][c[i]]
            );
            if (j >= 1) {//可以换 
                dp[i][j][1] = min(
                    dp[i-1][j-1][0] + (1 - k[i]) * dis[c[i-1]][c[i]] + k[i] * dis[c[i-1]][d[i]], 
                    dp[i-1][j-1][1] + 
                    (1 - k[i-1]) * (1 - k[i]) * dis[c[i-1]][c[i]] + 
                    (1 - k[i-1]) * k[i] * dis[c[i-1]][d[i]] + 
                    k[i-1] * (1 - k[i]) * dis[d[i-1]][c[i]] + 
                    k[i-1] * k[i] * dis[d[i-1]][d[i]]
                );
            }
        }
    }
    double ans = 1e18;
    for (int j = 0; j <= m; j++) {
        ans = min(ans, dp[n][j][0]);
        ans = min(ans, dp[n][j][1]);
    }
    printf("%.2lf", ans);
}