Title Description
For Niu Niu, who has just entered college, the first problem he faces is how to apply for appropriate courses according to the actual situation.
Among the optional courses, 2n courses are arranged in N time periods. In the I (1 < = I < = n) time period, two courses with the same content are held in different places at the same time, in which Niuniu is arranged to have classes in classroom ci in advance, and the other course is held in classroom di.
Without submitting any application, students need to complete all n scheduled courses in the order of time period. If students want to change the classroom of section I, they need to apply. If the application is approved, students can go to classroom di for class in the i-th time period, otherwise they still have class in classroom ci.
Because there is too much demand for classroom replacement, the application may not be passed. Through calculation, Niuniu found that when applying for changing the classroom of the i course, the probability of passing the application is a known real number ki, and the probability of passing for applications of different courses is independent of each other.
The school stipulates that all applications can only be submitted at one time before the beginning of the semester, and each person can only choose up to m courses to apply. This means that Niuniu must decide whether to apply for changing the classroom of each class at one time, but not whether to apply for other courses according to the application results of some courses; Niuniu can apply for the M courses he most wants to change the classroom, or he can {not finish these m application opportunities, or even not apply for a course.
Because different courses may be arranged in different classrooms, Niuniu needs to use recess time to rush from one classroom to another.
Niuniu's University has v classrooms and e roads. Each road connects two classrooms and can be {two-way traffic. Due to the different length of the road and the degree of congestion, the physical energy consumed through different roads may be different. When the I (1 < = I < = n-1) class is over, Niuniu will start from the classroom of this class and choose a "path" that consumes the least energy to go to the classroom of the next class.
Now Niuniu wants to know which courses can minimize his expectation of the sum of physical strength spent moving between classrooms. Please help him find the minimum value.
input
The first line contains four integers n, m, v, e. N represents the number of time periods in this semester; M indicates the maximum number of classes Niuniu can apply for to change; v represents the number of classrooms in Niuniu school; E is the number of roads in Niuniu's school.
The second line has n positive integers, and the I (1 < = I < = n) positive integer represents ci, that is, the classroom in which Niuniu is assigned to class in the i-th time period; Guarantee 1 < = ci < = v.
The third line has n positive integers, and the I (1 < = I < = n) positive integer represents di, that is, another classroom with the same course in the i-th time period; Guarantee 1 < = di < = v.
The fourth line has n real numbers, and the I (1 < = I < = n) real number represents Ki, that is, the probability that Niuniu's application to change the classroom in the i-th time period passes. Guarantee 0 < = ki < = 1.
Next, line e, each line has three positive integers aj, bj, wj, indicating that there is a two-way road connecting classrooms aj, bj, and the physical strength required to pass through this road is wj; Guarantee 1 < = aj, bj < = V, 1 < = wj < = 100.
Guarantee 1 < = n < = 2000, 0 < = m < = 2000, 1 < = V < = 300, 0 < = e < = 90000.
Ensure that all other classrooms can be reached from any classroom through the road in the school.
Ensure that the entered real number contains up to 3 decimal places.
output
Output a line containing a real number, rounded to exactly 2 digits after the decimal point, indicating the answer. Your output must be exactly the same as the standard output.
The test data shall ensure that the absolute value of the difference between the rounded answer and the accurate answer is not greater than 4 x 10^-3. (if you don't know what floating-point error is, this sentence can be understood as: for most algorithms, you can normally use floating-point type without special processing)
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
Tips
[example 1 Description]
All feasible application schemes and expected income are shown in the table below:
[prompt]
- There may be multiple two-way roads in the road connecting the same two classrooms. It is also possible that the same classroom is connected at both ends of the road.
- Please note the significance of distinguishing n, m, V and E. n ＾ is not the number of ＾ classrooms and m ＾ is not the number of ＾ roads.
[subtask]
Special property 1: between any two points AI, bi, AI ≠ bi on the graph, there is a path that consumes the least energy and contains only one road.
Special property 2: for all 1 < = I < = n, ki = 1.
#include <bits/stdc++.h>
using namespace std;
#define lson(u) (u<<1)
#define rson(u) (u<<1|1)
#define Pi acos(-1)
#define iINF 0x3f3f3f3f
#define lINF 0x3f3f3f3f3f3f3f
#define EPS 0.000000001
#define pii pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int MAXN1=2005;
const int MAXN2=305;
const ll Mod=1e9+7;
int n,m,v,e;
int C[MAXN1],D[MAXN1];
double K[MAXN1],f[MAXN1][MAXN1][2],dis[MAXN2][MAXN2];
void floyd()
{
for(int k=1;k<=v;k++)
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
void Init()
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
{
dis[i][j]=iINF;
}
}
for(int i=1;i<=v;i++)
{
dis[i][i] = 0;
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j][0]=f[i][j][1]=iINF;
}
}
}
int main()
{
int x,y,xy;
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;i++)
{
scanf("%d",&C[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&D[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%lf",&K[i]);
}
Init();
for(int i=0;i<e;i++)
{
scanf("%d%d%d",&x,&y,&xy);
dis[x][y]=min(dis[x][y],double(xy));
dis[y][x]=min(dis[y][x],double(xy));
}
floyd();
double dis1,dis2;
double ans=iINF;
f[1][0][0]=f[1][1][1]=0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=m&&j<=i;j++)
{
dis1=dis[C[i]][C[i-1]];
dis2=dis[C[i]][D[i-1]]*K[i-1] + dis[C[i]][C[i-1]]*(1.0-K[i-1]);
if(j==0)
{
f[i][j][0]=f[i-1][j][0]+dis1;
}
else
{
f[i][j][0] = min(f[i-1][j][0] + dis1, f[i-1][j][1] + dis2);
}
if(j == 0)
{
continue;
}
dis1=dis[D[i]][C[i-1]]*K[i]+dis[C[i]][C[i-1]]*(1.0-K[i]);
dis2=dis[D[i]][D[i-1]]*K[i]*K[i-1]+dis[D[i]][C[i-1]]*K[i]*(1.0-K[i-1])+dis[C[i]][D[i-1]]*(1.0-K[i])*K[i-1]+dis[C[i]][C[i-1]]*(1.0-K[i])*(1.0-K[i-1]);
f[i][j][1]=min(f[i-1][j-1][0]+dis1,f[i-1][j-1][1]+dis2);
}
}
for(int j=0;j<=m&&j<=n;j++) {
ans=min(ans,f[n][j][0]);
ans=min(ans,f[n][j][1]);
}
printf("%0.2lf",ans);
return 0;
}