33264번 - Edges and Divisors 다국어

We play a game on a directed acyclic graph $G = (V, E)$. We start at vertex $s_1 \in V$. The rules of the game are as follows:

• The game consists of rounds numbered from $1$.
• In the $i$-th round, the player selects a path $p_i$ starting from $s_i$ and containing at least one edge such that the sum of the weights of all edges belonging to this path is an exact multiple of $(i + 1)$. If the player cannot select such a path, the player has failed, and will not score any points. Otherwise, the round ends successfully, and the endpoint of $p_i$ is recorded as $s_{i + 1}$.
• After a successful round, the player can either end the game or continue with the next round. If the player chooses to end the game, the selected $i$ paths $p_1, \ldots, p_i$ are called doubling paths, and the score is calculated.

If the player has not failed, then when ending the game, for the selected doubling paths $p_1, \ldots, p_k$, the score of the game is defined as $\sum_{i = 1}^{k} a_i \left|p_i\right| / k$, where $|p_i|$ represents the number of edges in path $p_i$, and $a_i$ is the weight given in the input. Clearly, as the graph is acyclic, at most $(n-1)$ paths can be selected, so the input only provides the weights $a_1, \ldots, a_{n-1}$.

Given the graph and the starting vertex, calculate the maximum achievable score in the game.

The first line of input contains three integers, $n$, $m$, and $s_1$: the number of vertices, the number of edges, and the index of the starting vertex ($2 \le n \le 100$; $1 \le m \le \frac{n (n - 1)}{2}$; $1 \le s_1 \le n$).

The second line contains $(n-1)$ integers $a_1, \ldots, a_{n-1}$: the weights used to calculate the score ($1 \le a_1 \le a_2 \le \ldots \le a_{n - 1} \le 10^9$).

Each of the next $m$ lines contains three integers, $u_i$, $v_i$, and $w_i$, describing a directed edge from $u_i$ to $v_i$ with weight $w_i$ ($1 \le u_i, v_i \le n$; $u_i \ne v_i$; $1 \le w_i \le 10^9$). It is guaranteed that the graph is acyclic, the graph is connected if we treat edges as undirected, and there are no multiple edges.

Output a single line containing two integers separated by a space.

If at least one path can be selected, there exists an optimal selection scheme that maximizes the score, and the optimal score can be represented as $p/q$ where $p$ and $q$ are coprime integers and $q > 0$. In this case, output $p$ and $q$. Otherwise (if it is impossible to select any paths), output "-1~-1".

The selected doubling paths are $p_1 = ((1, 2))$ and $p_2 = ((2, 5))$.