P7591 Hunting (2021 CoE-II D)

In the territory of the lioness $\text{Dina}$, there are $n$ fixed hunting spots. At hunting spot $i$, the probability of catching prey is $p_i$. There are several directly connected bidirectional roads among Dina’s den (nest) and the $n$ hunting spots. Every morning, $\text{Dina}$ starts from her den and randomly chooses a hunting spot $u$ that is adjacent to the den to hunt once. If she does not catch prey, she will randomly choose another hunting spot $v$ that is adjacent to the current hunting spot $u$ and hunt once again. If she still does not catch prey at hunting spot $v$, she will continue hunting following the same process. If she catches prey at some hunting spot, she will immediately return to the den and end the hunt. If the current hunting spot $u$ is adjacent to the den but is not adjacent to any other hunting spot, $\text{Dina}$ will also choose to return to the den immediately, and then randomly choose one hunting spot adjacent to the den to continue the hunting process described above. At each hunting spot, $\text{Dina}$ hunts exactly once and then leaves, but she may return to the same spot later to hunt again. In this problem, if there is a directly connected bidirectional road between location $u$ and location $v$, then $u$ and $v$ are called **adjacent**; otherwise they are called **non-adjacent**. Let the den be numbered $0$, and the $n$ hunting spots be numbered from $1$ to $n$. Moving from location $u$ to location $v$ costs $h_{u,v}$ stamina and $t_{u,v}$ time. Each time $\text{Dina}$ hunts at hunting spot $i$, she consumes $h_i$ stamina and $t_i$ time. Each time $\text{Dina}$ arrives at a hunting spot and finishes one hunt there, she evaluates her stamina consumption and time spent. If her stamina consumption has reached (or exceeded) the limit $H$, she immediately returns to the den and ends the hunt. If her time spent has reached (or exceeded) the limit $T$, she also immediately returns to the den and ends the hunt. $\text{Dina}$ only evaluates after arriving at a hunting spot and completing one hunt; she does not evaluate at any other moment. If she is currently at the den, she evaluates as soon as she arrives at the den, because there is no prey to catch at the den. Note that $\text{Dina}$ does not evaluate while moving along a road between two locations. Therefore, it is possible that when she arrives at a hunting spot but has not hunted yet, her stamina consumption or time spent has already exceeded the limit. In this case, $\text{Dina}$ will still perform one hunt, and only then evaluate. When $\text{Dina}$ returns to the den because she successfully catches prey, or because her stamina consumption or time spent reaches (or exceeds) the corresponding limit, or because the current hunting spot is non-adjacent to all other hunting spots, she always chooses a path with the minimum total time to return to the den. If there are multiple paths with the minimum total time, she chooses the one with the minimum total stamina consumption. During the return to the den, $\text{Dina}$ does not hunt. The whole process starting from leaving the den, and then returning to the den and ending the hunt due to one of the following three conditions: - successful hunting, - stamina consumption reaching (or exceeding) the limit $H$, - time spent reaching (or exceeding) the limit $T$, is called one hunting. Given the roads between the den and hunting spots, the stamina and time cost of each road, the probability of catching prey at each hunting spot, and the stamina and time cost of hunting once at each hunting spot, determine the expected (average) stamina consumption and time spent for $\text{Dina}$ to complete one hunting.

The first line contains an integer $n$, denoting the number of hunting spots. The next $n$ lines each contain three values: an integer $h_i$, an integer $t_i$, and a real number $p_i$, denoting the stamina consumed, the time spent, and the probability of catching prey for one hunt at hunting spot $i$, respectively. Next is an integer $m$, denoting the number of bidirectional roads connecting the locations. The following $m$ lines each contain four integers $u$, $v$, $h_{u,v}$, $t_{u,v}$, indicating that there is a directly connected road between location $u$ ($0 \le i \le n$) and location $v$ ($0 \le i \le n$, $u \ne v$), which costs $h_{u,v}$ stamina and $t_{u,v}$ time. Since the road is bidirectional, the stamina and time costs are the same in both directions. The last line contains two integers $H$ and $T$, denoting the limits of stamina and time, respectively.

Output one line containing two real numbers, accurate to one digit after the decimal point, representing the expected stamina consumption and expected time spent for $\text{Dina}$ to complete one hunting. Your output is considered correct if the absolute error from the reference output is less than $10^{-1}$.

**Subtasks are scored with bundled testdata.** **Sample Explanation** Input #1  This input contains only one hunting spot. The road from the den to hunting spot $1$ costs $2$ stamina and $3$ time. The stamina limit is $10$, and the time limit is $20$. One hunt at hunting spot $1$ costs $1$ stamina and $2$ time. The probability of catching prey at hunting spot $1$ is $1.00$, meaning Dina will definitely catch prey. It is easy to see that the expected stamina consumption and time spent for one hunting are $5.0=(2+1+2) \times 100\%$ and $8.0=(3+2+3) \times 100\%$, respectively. Input #2  Compared with the first input, two more hunting spots are added, but only hunting spot $1$ and hunting spot $2$ are directly connected to the den by roads. There are no direct roads among the three hunting spots, but hunting spot $1$ can be indirectly connected to hunting spot $2$ through the den. The road from the den to hunting spot $2$ costs $4$ stamina and $5$ time, and one hunt at hunting spot $2$ costs $2$ stamina and $3$ time. The probability of catching prey at hunting spot $1$ is $1.00$, meaning Dina will definitely catch prey, so $\text{Dina}$ will immediately return to the den and end the hunt. The probability of catching prey at hunting spot $2$ is $0.50$, meaning there is a $50\%$ chance to catch prey, but since hunting spot $2$ has no other hunting spot directly connected to it, regardless of whether Dina catches prey at hunting spot $2$, she will choose to return to the den immediately. When returning to the den, she has already consumed $10$ stamina. According to the statement, regardless of whether Dina has caught prey, she will end the hunt. Since the initial choice is random, the probabilities of choosing hunting spot $1$ and $2$ from the den are both $50\%$. By calculation, the expected stamina consumption and expected time spent for one hunting are $7.5=(2+1+2) \times 50\%+(4+2+4) \times 50\%$ and $10.5=(3+2+3) \times 50\%+(5+3+5) \times 50\%$, respectively. ------------ **Constraints** - Subtask $1$: $n=1$, $10$ points. - Subtask $2$: $1 \le n \le 20$, no hunting spot has a direct road to any other hunting spot, $20$ points. - Subtask $3$: no special restrictions, $70$ points. For $100\%$ of the testdata: $1 \le n \le 200$, $1 \le h_i \le 10$, $1 \le t_i \le 10$, $0 \le p_i \le 1$, $1 \le m \le \text{min}(n (n+1) / 2$，$2000$), $1 \le h_{u,v} \le 20$, $1 \le t_{u,v} \le 20$, $1 \le H \le 200$, $1 \le T \le 200$. ------------ **Conventions** - Between locations $u$ and $v$, there is at most one directly connected bidirectional road, and the same direct bidirectional road will not be given repeatedly. - Ignore the time needed for $\text{Dina}$ to perform evaluations. - In the input, the value representing the probability $p_i$ is a real number with two digits after the decimal point. Translated by ChatGPT 5