CF1482F Useful Edges

给定一个有 $n$ 个顶点的带权无向图，以及 $q$ 个三元组 $(u, v, l)$，其中每个三元组中 $u$ 和 $v$ 是顶点，$l$ 是一个正整数。对于一条边 $e$，如果存在至少一个三元组 $(u, v, l)$ 和一条路径（不一定简单路径），满足以下条件： - $u$ 和 $v$ 是该路径的两个端点， - $e$ 是该路径上的一条边， - 该路径上所有边的权值之和不超过 $l$， 则称这条边 $e$ 是有用的。 请输出该图中有用的边的数量。

第一行包含两个整数 $n$ 和 $m$（$2\leq n\leq 600$，$0\leq m\leq \frac{n(n-1)}{2}$）。 接下来的 $m$ 行，每行包含三个整数 $u$、$v$ 和 $w$（$1\leq u, v\leq n$，$u\neq v$，$1\leq w\leq 10^9$），表示一条连接顶点 $u$ 和 $v$ 的权值为 $w$ 的边。 接下来一行包含一个整数 $q$（$1\leq q\leq \frac{n(n-1)}{2}$），表示三元组的数量。 接下来的 $q$ 行，每行包含三个整数 $u$、$v$ 和 $l$（$1\leq u, v\leq n$，$u\neq v$，$1\leq l\leq 10^9$），表示一个三元组 $(u, v, l)$。 保证： - 图中没有自环和重边； - 所有三元组中的 $(u, v)$ 对也都不同。

输出一个整数，表示图中有用的边的数量。

在第一个样例中，除了权值为 $5$ 的那条边外，其余每条边都是有用的。 在第二个样例中，只有 $1$ 和 $2$ 之间的边是有用的，因为它属于路径 $1-2$，且 $10\leq 11$。而 $3$ 和 $4$ 之间的边则不是有用的。 在第三个样例中，两条边都是有用的，因为存在一条长度恰好为 $5$ 的路径 $1-2-3-2$。注意，路径可以经过某个顶点多次。 由 ChatGPT 4.1 翻译