← 返回题目列表

Codeforces · 1482/F

F. 有用的边缘

中文机器翻译题面 查看原题

给您一个 $$$n$$$ 顶点上的加权无向图以及 $$$q$$$ 三元组 $$$(u, v, l)$$$,其中每个三元组 $$$u$$$ 和 $$$v$$$ 是顶点,$$$l$$$ 是正整数。如果至少有一个三元组 $$$(u, v, l)$$$ 和一条具有以下属性的路径(不一定简单),则称边 $$$e$$$ 有用:

- $$$u$$$ 和 $$$v$$$ 是该路径的端点,
- $$$e$$$ 是这条路径的边缘之一,
- 该路径上所有边的权重总和不超过 $$$l$$$。

请打印出该图中有用边的数量。

输入

第一行包含两个整数 $$$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)$$$ 也不同。

输出

打印一个整数,表示图中有用边的数量。

示例

输入 #1

4 6
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3
1 4 5
1
1 4 4

输出 #1

5

输入 #2

4 2
1 2 10
3 4 10
6
1 2 11
1 3 11
1 4 11
2 3 11
2 4 11
3 4 9

输出 #2

1

输入 #3

3 2
1 2 1
2 3 2
1
1 2 5

输出 #3

2

注意

在第一个示例中,除了权重 $$$5$$$ 的边之外,每条边都是有用的。

在第二个示例中,只有 $$$1$$$ 和 $$$2$$$ 之间的边有用,因为它属于路径 $$$1-2$$$ 和 $$$10 \leq 11$$$。另一方面,$$$3$$$ 和 $$$4$$$ 之间的边缘没有用。

在第三个示例中,两条边都很有用,因为有一条路径 $$$1-2-3-2$$$ 的长度恰好为 $$$5$$$。请注意,路径可能多次经过一个顶点。