CF1900E Transitive Graph

给定一个有向图 $G$，包含 $n$ 个顶点和 $m$ 条边。 初始时，图 $H$ 与图 $G$ 相同。接下来你决定进行如下操作： - 如果在 $H$ 中存在三个顶点 $a$、$b$、$c$，使得存在一条从 $a$ 到 $b$ 的边和一条从 $b$ 到 $c$ 的边，但不存在从 $a$ 到 $c$ 的边，则添加一条从 $a$ 到 $c$ 的边。 - 只要还存在这样的三元组，就重复上述步骤。 注意，经过操作后，$H$ 中的边数最多可以达到 $n^2$。 你还在 $H$ 的每个顶点上写了一个数。具体来说，第 $i$ 个顶点上写着 $a_i$。 考虑一条由 $k$ 个不同顶点 $v_1, v_2, \ldots, v_k$ 组成的简单路径。该路径的长度为 $k$。该路径的权值定义为 $\sum_{i = 1}^k a_{v_i}$。 如果不存在比该路径更长的简单路径，则称其为最长简单路径。 在所有 $H$ 中的最长简单路径中，找出权值最小的那一条。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示顶点数和边数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示每个顶点上写的数。 接下来的 $m$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$），表示图 $G$ 中存在一条从 $v_i$ 到 $u_i$ 的有向边。注意，边是有向的，且图中可能存在自环和重边。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \times 10^5$。

对于每个测试用例，输出两个数——$H$ 中最长简单路径的长度，以及该路径的最小可能权值。

在第一个测试用例中，两图中的最长路径为 $1 \to 3 \to 4 \to 5 \to 2$。由于该路径包含所有顶点，最长路径的最小权值为所有顶点权值之和，即 $12$。 在第二个测试用例中，最长路径为 $1 \to 2 \to 3 \to 4 \to 6 \to 7$。由于没有包含顶点 $5$ 的最长路径，该路径的最小权值为 $5\,999\,999\,995$。 在第三个测试用例中，可以证明不存在长度超过 $11$ 的路径，且最长路径的权值不会小于 $37$。注意，给定的图中既有自环也有重边。 由 ChatGPT 4.1 翻译