P8418 [THUPC 2022 Finals] Doubling Paths

For any DAG $G=(V,E)$ and a starting vertex $s_1\in V$ in the graph, the rules of the doubling mini-game are as follows: - In the $i$-th round of operation ($i=1,2,\cdots$), the player chooses a **non-empty** path $p_i$ starting from $s_i$, such that the sum of edge weights along this path is exactly a multiple of $(i+1)$. If it is impossible to choose a path that satisfies the multiple requirement, then the game is considered failed, and the player will receive no score. Otherwise, this round is successful, and the endpoint of $p_i$ is recorded as $s_{i+1}$. - After the $i$-th round is successful, the player may choose to end the game or continue to the $(i+1)$-th round. If the player chooses to end the game, then the chosen $i$ paths $p_1, \cdots, p_i$ are called doubling paths, and the score is calculated. If the game does not fail, when ending the game, for the selected doubling paths $p_1, \cdots, p_k$, the score is defined as $\sum_{i=1}^k a_i \left|p_i\right|/k$, where $|p_i|$ denotes the number of edges in path $p_i$, and $a_i$ is the given weight from the input. Obviously, no matter how the paths are chosen, at most $(n-1)$ paths can be selected, so the input only provides $a_1, \cdots, a_{n-1}$. To set the clearance requirement for each graph, given the DAG and the starting vertex, compute the maximum possible score of this game.

The first line contains three positive integers $n$, $m$, $s_1$ separated by spaces, representing the number of vertices, the number of edges, and the index of the starting vertex. It is guaranteed that $2\le n \le 100$, $1\le m\le \frac{n(n-1)}{2}$, and $1\le s_1\le n$. The second line contains $(n-1)$ positive integers $a_1, \cdots, a_{n-1}$ separated by spaces, representing the weights used when calculating the score. It is guaranteed that $1\le a_1\le a_2\le\cdots\le a_{n-1}\le 10^9$. In the next $m$ lines, each line contains three positive integers $u_i, v_i, w_i$ separated by spaces, describing a directed edge from $u_i$ to $v_i$ with weight $w_i$. It is guaranteed that $1\le u_i, v_i\le n$, $u_i\ne v_i$, $1\le w_i\le 10^9$, the graph is connected, and there are no multiple edges.

Output exactly one line containing two integers separated by a space. If at least one path can be selected, then there exists an optimal selection that maximizes the score. Let the simplest fractional form of this optimal score be $p/q$ (if the optimal score is an integer, take $q=1$), and output $p$ and $q$. Otherwise, if it is impossible to select at least one path no matter what, output `-1 -1`.

[Sample 1 Explanation] The selected doubling paths are $p_1 = ((1, 2)), p_2 = ((2, 5))$. [Constraints] For $100\%$ of the testdata, it is guaranteed that $2\le n\le 100$, $1\le m\le \frac{n(n-1)}{2}$, $1\le s_1, u_i, v_i\le n$, $1\le a_1 \le \cdots\le a_{n-1}\le 10^9$, $1\le w_i\le 10^9$, the input graph is connected, and there are no multiple edges. Translated by ChatGPT 5