CF1870H Standard Graph Problem

给定一个有 $n$ 个顶点和 $m$ 条边的带权有向图。图中的每个顶点可以是高亮的或普通的。初始时，所有顶点都是普通的。图的代价被定义为：选择若干条边，使得从每个普通顶点出发，仅通过被选择的边，至少可以到达一个高亮顶点，这些被选择的边的权值之和的最小值。如果无法选择出满足条件的边集，则代价为 $-1$。 你的任务是，在每次 $q$ 次操作后，计算当前图的代价。操作有两种类型： - $+\;v_i$：将顶点 $v_i$ 设为高亮，保证操作前该顶点为普通顶点。 - $-\;v_i$：将顶点 $v_i$ 设为普通，保证操作前该顶点为高亮顶点。 每次操作后，输出当前图的代价。

第一行包含三个整数 $n$、$m$ 和 $q$（$3 \le n \le 2 \cdot 10^5, 1 \le m, q \le 2 \cdot 10^5$），分别表示顶点数、边数和操作数。 接下来 $m$ 行，每行三个整数 $u_i$、$v_i$、$c_i$（$1 \leq u_i, v_i \leq n, u_i \ne v_i, 1 \leq c_i \leq 10^6$），表示一条从 $u_i$ 到 $v_i$ 的有向边及其权值。 接下来 $q$ 行，每行一个操作，格式为 $+\;v_i$ 或 $-\;v_i$（$1 \leq v_i \leq n$）。

输出 $q$ 个数字，第 $i$ 个数字表示前 $i$ 次操作后的图的代价。

在第一个测试样例中： - 第一次操作后，最优选择第 $3, 4, 5$ 条边，总代价为 $15$。 - 第二次操作后，没有高亮顶点，无法满足条件，代价为 $-1$。 - 第三次操作后，最优选择第 $1, 2, 5$ 条边，总代价为 $14$。 - 第四次操作后，最优选择第 $4, 5$ 条边，总代价为 $12$。 - 第五次操作后，最优选择第 $5$ 条边，代价为 $4$。 - 第六次操作后，所有顶点均为高亮，无需选择任何边，代价为 $0$。 由 ChatGPT 4.1 翻译