P2784 Chemistry 1 (chem1) - Chemical Synthesis

The juruo HansBug scratched his head countless times in the chemistry exam, yet his mind was still blank.

In front of the juruo HansBug is a chemical synthesis problem. As far as he knows, answers are usually written in the following format:  (continued on the next line)  A brief explanation: each compound can produce another compound through a one-step reaction (call this a one-step reaction, denoted as $A \rightarrow B$). Now assume that in each $A \rightarrow B$, theoretically $1$ unit of $A$ can only produce $1$ unit of $B$. However, actual experiments show that perfectly complete chemical conversion does not exist. Let the conversion rate be $C$ (i.e., $1$ unit of $A$ actually produces $C$ units of $B$, where $0 < C < 1$). In the juruo HansBug’s knowledge base there are $N$ such $A \rightarrow B$ conversions. In this problem, HansBug needs to produce compound $T$ starting from $1$ unit of compound $S$. But his brain cells and RP are exhausted, so the arduous task of finding the synthesis route with the highest final yield is handed over to you!

The first line contains four integers: $N, M, S, T$, representing the total number of distinct compounds, the number of reactions known to HansBug, the index of the starting compound, and the index of the target compound, respectively ($1 \le S, T \le N$). Lines $2$ to $M+1$ each contain two integers and one real number: $A_i, B_i, C_i$, indicating that the $i$-th reaction converts $1$ unit of compound $A_i$ into $C_i$ units of compound $B_i$.

Output one line containing a real number: the final yield along the optimal route (rounded to $4$ decimal places). If there is no feasible route, output `orz`.

In Sample $1$ and Sample $2$, the two synthesis routes are $1 \rightarrow 3$, $1 \rightarrow 2$, $2 \rightarrow 3$, with yields $0.8$, $0.9$, $0.9$, respectively. In Sample $1$, there are two feasible routes, $1 \rightarrow 3$ and $1 \rightarrow 2 \rightarrow 3$. Their final yields are $0.8$ and $0.9 \times 0.9 = 0.81$, respectively, so the second route is better, with a yield of $0.8100$. In Sample $2$, $2$ can only produce $3$, and $3$ cannot produce any other compound, so synthesis is impossible, and the juruo HansBug has to output `orz`. Constraints  Translated by ChatGPT 5