| 12345678 |
- #include <algorithm>
- #include <array>
- #include <iomanip>
- #include <iostream>
- #include <limits>
- #include <vector>
- using namespace std;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m,v,e;cin>>n>>m>>v>>e;vector<int>c(n),d(n);vector<double>p(n);for(int&x:c)cin>>x,--x;for(int&x:d)cin>>x,--x;for(double&x:p)cin>>x;const int INF=1e9;vector<vector<int>>dis(v,vector<int>(v,INF));for(int i=0;i<v;++i)dis[i][i]=0;while(e--){int a,b,w;cin>>a>>b>>w;--a;--b;dis[a][b]=dis[b][a]=min(dis[a][b],w);}for(int k=0;k<v;++k)for(int i=0;i<v;++i)for(int j=0;j<v;++j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);const double BIG=numeric_limits<double>::infinity();vector<vector<array<double,2>>>dp(n,vector<array<double,2>>(m+1,{BIG,BIG}));dp[0][0][0]=0;if(m)dp[0][1][1]=0;for(int i=1;i<n;++i)for(int j=0;j<=min(m,i+1);++j){if(j<=i){dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+dis[c[i-1]][c[i]]);dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+(1-p[i-1])*dis[c[i-1]][c[i]]+p[i-1]*dis[d[i-1]][c[i]]);}if(j){dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][0]+(1-p[i])*dis[c[i-1]][c[i]]+p[i]*dis[c[i-1]][d[i]]);dp[i][j][1]=min(dp[i][j][1],dp[i-1][j-1][1]+(1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]+(1-p[i-1])*p[i]*dis[c[i-1]][d[i]]+p[i-1]*(1-p[i])*dis[d[i-1]][c[i]]+p[i-1]*p[i]*dis[d[i-1]][d[i]]);}}double ans=BIG;for(int j=0;j<=m;++j)ans=min({ans,dp[n-1][j][0],dp[n-1][j][1]});cout<<fixed<<setprecision(2)<<ans<<'\n';}
|
