P1850 [NOIP 2016 Senior] Switching Classrooms

NOIP 2016 Senior D1T3.

For Niuniu, who has just entered university, the first problem he faces is how to apply for suitable courses according to the actual situation. Among the selectable courses, there are $2n$ classes scheduled across $n$ time slots. In the $i$-th time slot ($1 \le i \le n$), two classes with the same content are held simultaneously at different locations. Niuniu is pre-assigned to attend the class in classroom $c_i$, while the other class is in classroom $d_i$. Without submitting any applications, students follow the order of time slots to complete all $n$ scheduled classes one by one. If a student wants to switch the classroom for the $i$-th class, they need to submit an application. If the application is approved, the student will attend the class in classroom $d_i$ during the $i$-th time slot; otherwise, they will still attend in classroom $c_i$. Because there are too many requests to switch classrooms, an application may not be approved. Through calculation, Niuniu finds that when applying to switch the classroom for the $i$-th class, the probability that the application is approved is a known real number $k_i$, and the approval events for different classes are independent. The school stipulates that all applications must be submitted once before the start of the term, and each person may choose to apply for at most $m$ classes. This means that Niuniu must decide all at once whether to apply to switch the classroom for each class, and cannot decide whether to apply for other classes based on the approval results of some classes. Niuniu can apply for the $m$ classes he most wants to switch, he may also use fewer than $m$ application opportunities, or even apply for none. Because different classes may be arranged in different classrooms, Niuniu needs to use break time to travel from one classroom to another. Niuniu’s university has $v$ classrooms and $e$ roads. Each road connects two classrooms and is bidirectional. Because road lengths and congestion vary, the stamina consumed when traversing different roads may differ. After the $i$-th class ends ($1 \le i \le n - 1$), Niuniu will depart from the classroom of that class and choose a path with the minimum stamina cost to reach the classroom of the next class. Now Niuniu wants to know which classes he should apply for so that the expected value of the total stamina cost due to moving between classrooms is minimized. Please help him compute this minimum value.

The first line contains four integers $n, m, v, e$. $n$ is the number of time slots in this term; $m$ is the maximum number of classes for which Niuniu may apply to switch classrooms; $v$ is the number of classrooms in the school; $e$ is the number of roads in the school. The second line contains $n$ positive integers. The $i$-th ($1 \le i \le n$) integer is $c_i$, the classroom where Niuniu is scheduled to attend in the $i$-th time slot. It is guaranteed that $1 \le c_i \le v$. The third line contains $n$ positive integers. The $i$-th ($1 \le i \le n$) integer is $d_i$, the classroom of the other class with the same content in the $i$-th time slot. It is guaranteed that $1 \le d_i \le v$. The fourth line contains $n$ real numbers. The $i$-th ($1 \le i \le n$) real number is $k_i$, the probability that Niuniu’s application to switch the classroom in the $i$-th time slot is approved. It is guaranteed that $0 \le k_i \le 1$. The next $e$ lines each contain three positive integers $a_j, b_j, w_j$, indicating a bidirectional road connecting classrooms $a_j$ and $b_j$, and traversing this road consumes stamina $w_j$. It is guaranteed that $1 \le a_j, b_j \le v$ and $1 \le w_j \le 100$. It is guaranteed that $1 \le n \le 2000$, $0 \le m \le 2000$, $1 \le v \le 300$, and $0 \le e \le 90000$. It is guaranteed that using the school’s roads, every classroom is reachable from any other classroom. It is guaranteed that each input real number has at most $3$ decimal places.

Output one line containing a real number, rounded to exactly $2$ decimal places, which is the answer. Your output must be exactly the same as the standard output to be considered correct. The testdata guarantees that the absolute difference between the rounded answer and the exact answer is at most $4 \times 10^{-3}$. (If you do not know what floating-point error is, you can understand this as: for most algorithms, you can normally use floating-point types without special handling.)

Sample 1 explanation. All feasible application plans and their expected stamina costs are as follows: - No application submitted. The expected stamina cost is $8.0$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | None | $1.0$ | $8$ | - Apply to switch the classroom in the $1$-st time slot. The expected stamina cost is $4.8$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | $1$ | $0.8$ | $4$ | | None | $0.2$ | $8$ | - Apply to switch the classroom in the $2$-nd time slot. The expected stamina cost is $6.4$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | $2$ | $0.2$ | $0$ | | None | $0.8$ | $8$ | - Apply to switch the classroom in the $3$-rd time slot. The expected stamina cost is $6.0$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | $3$ | $0.5$ | $4$ | | None | $0.5$ | $8$ | - Apply to switch the classroom in the $1$-st and $2$-nd time slots. The expected stamina cost is $4.48$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | $1,2$ | $0.16$ | $4$ | | $1$ | $0.64$ | $4$ | | $2$ | $0.04$ | $0$ | | None | $0.16$ | $8$ | - Apply to switch the classroom in the $1$-st and $3$-rd time slots. The expected stamina cost is $2.8$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | $1,3$ | $0.4$ | $0$ | | $1$ | $0.4$ | $4$ | | $3$ | $0.1$ | $4$ | | None | $0.1$ | $8$ | - Apply to switch the classroom in the $2$-nd and $3$-rd time slots. The expected stamina cost is $5.2$. | Time slots approved | Probability | Stamina cost | | :--------: | :----: | :----: | | $2,3$ | $0.1$ | $4$ | | $2$ | $0.1$ | $0$ | | $3$ | $0.4$ | $4$ | | None | $0.4$ | $8$ | Therefore, the optimal plan is to apply to switch the classroom in the $1$-st and $3$-rd time slots. The expected stamina cost is $2.8$. Notes. 1. There may be multiple bidirectional roads connecting the same pair of classrooms. It is also possible for a road to connect a classroom to itself. 2. Please distinguish the meanings of $n, m, v, e$. $n$ is not the number of classrooms, and $m$ is not the number of roads. Constraints and Notes. | Test set ID | $n \le$ | $m \le$ | $v \le$ | Has Special Property 1 | Has Special Property 2 | | :--------: | :----: | :----: | :----: | :----------------: | :----------------: | | 1 | $1$ | $1$ | $300$ | $\times$ | $\times$ | | 2 | $2$ | $0$ | $20$ | $\times$ | $\times$ | | 3 | $2$ | $1$ | $100$ | $\times$ | $\times$ | | 4 | $2$ | $2$ | $300$ | $\times$ | $\times$ | | 5 | $3$ | $0$ | $20$ | $\surd$ | $\surd$ | | 6 | $3$ | $1$ | $100$ | $\surd$ | $\times$ | | 7 | $3$ | $2$ | $300$ | $\times$ | $\times$ | | 8 | $10$ | $0$ | $300$ | $\surd$ | $\surd$ | | 9 | $10$ | $1$ | $20$ | $\surd$ | $\times$ | | 10 | $10$ | $2$ | $100$ | $\times$ | $\times$ | | 11 | $10$ | $10$ | $300$ | $\times$ | $\surd$ | | 12 | $20$ | $0$ | $20$ | $\surd$ | $\times$ | | 13 | $20$ | $1$ | $100$ | $\times$ | $\times$ | | 14 | $20$ | $2$ | $300$ | $\surd$ | $\times$ | | 15 | $20$ | $20$ | $300$ | $\times$ | $\surd$ | | 16 | $300$ | $0$ | $20$ | $\times$ | $\times$ | | 17 | $300$ | $1$ | $100$ | $\times$ | $\times$ | | 18 | $300$ | $2$ | $300$ | $\surd$ | $\surd$ | | 19 | $300$ | $300$ | $300$ | $\times$ | $\surd$ | | 20 | $2000$ | $0$ | $20$ | $\times$ | $\times$ | | 21 | $2000$ | $1$ | $20$ | $\times$ | $\times$ | | 22 | $2000$ | $2$ | $100$ | $\times$ | $\times$ | | 23 | $2000$ | $2000$ | $100$ | $\times$ | $\times$ | | 24 | $2000$ | $2000$ | $300$ | $\times$ | $\times$ | | 25 | $2000$ | $2000$ | $300$ | $\times$ | $\times$ | Special Property 1: For any two distinct nodes $u, v$ in the graph, there exists a minimum-stamina path that consists of only one road. Special Property 2: For all $1 \le i \le n$, $k_i = 1$. Translated by ChatGPT 5