题目描述

对于任意一张 DAG $G=(V,E)$ 和图中的一个起始点 $s_1\in V$，倍增小游戏的规则为：

• 在第 $i$ 轮操作（$i=1,2,\cdots$）中，玩家选取一条起点为 $s_i$ 的非空路径 $p_i$，使得所有属于这条路径的边的边权和恰为 $(i+1)$ 的倍数。如果无法选择出满足倍数要求的路径，则称游戏失败，玩家将不会获得任何分数；否则，本轮操作成功，并记 $p_i$ 的终点为 $s_{i+1}$。

• 在第 $i$ 轮操作成功后，玩家可以选择结束游戏或者继续第 $(i+1)$ 轮操作。如果选择结束游戏，则称选择出的 $i$ 条路径 $p_1, \cdots, p_i$ 为倍增路径，并计算得分。

如果游戏没有失败，则在结束游戏时，对于选出的倍增路径 $p_1, \cdots, p_k$，定义游戏的分数为 $\sum_{i=1}^k a_i \left|p_i\right|/k$，其中 $|p_i|$ 表示路径 $p_i$ 包含的边数，$a_i$ 是输入给定的权值。显然，无论如何选取路径，最多也只能选出 $(n-1)$ 条路径，因此输入中只给出了 $a_1, \cdots, a_{n-1}$。

为了设置每张图的通关要求，请对给出的 DAG 和起始点，计算该游戏的最大分数。

输入格式

输入的第一行包含三个由空格隔开的正整数 $n$，$m$，$s_1$，表示给出的图中点的数量、边的数量及起始点的编号。保证 $2\le n \le 100$，$1\le m\le \frac{n(n-1)}{2}$，$1\le s_1\le n$。

输入的第二行包含 $(n-1)$ 个由空格隔开的正整数 $a_1, \cdots, a_{n-1}$，表示计算分数时的权重。保证 $1\le a_1\le a_2\le\cdots\le a_{n-1}\le 10^9$。

接下来 $m$ 行，每行输入三个由空格隔开的正整数 $u_i, v_i, w_i$，描述图中一条由 $u_i$ 连向 $v_i$，权值为 $w_i$ 的单向边。保证 $1\le u_i, v_i\le n$，$u_i\ne v_i$，$1\le w_i\le 10^9$，图是连通的且没有重边。

输出格式

输出仅一行，包括两个整数，由空格隔开。

如果可以选出至少一条路径，则存在一种最优的选取方案使得分数最大，记这个最优分数的最简分数表示为 $p/q$（当最优分数恰为整数时认为 $q=1$），则输出 $p$，$q$。否则，如果无论如何选取都无法选取出至少一条路径，则输出 -1 -1。

5 5 1
1 11 21 1211
1 2 4
1 3 11
2 5 9
3 4 12
4 5 13

6 1

9 16 1
1 10 100 1000 10000 100000 1000000 10000000
1 2 2
1 3 3
2 3 5
2 5 7
3 4 11
3 5 13
3 6 17
3 7 19
4 7 23
5 6 29
5 8 31
6 7 37
6 8 41
6 9 43
7 9 47
8 9 53

221 3

数据范围与提示

对于 $100\%$ 的数据，保证 $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$，输入的图是连通的且没有重边。

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2022。

题解等资源可在 https://github.com/THUSAAC/THUPC2022-Final 查看。