Useful Edges

题意翻译

### 题目描述 先有一 $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 \dfrac{n(n-1)}{2}$）. 接下来 $m$ 行，每行三个整数 $u$，$v$ 与 $w$ （$1 \leq u$，$v \leq n$，$1 \leq w \leq 10^9$）。表示连接顶点 $u$ 和 $v$ 的边权重为 $w$。 接下来一行一个整数 $q$ （$1 \leq q \leq \dfrac{n(n-1)}{2} $），表示三元组的数量。 接下来 $q$ 行，每行三个整数 $u$，$v$ 与 $l$ （$1 \leq u$，$v \leq n$，$u \ne v$，$1 \leq l \leq 10^9$ ），表示三元组 $u,v,l$。 输入保证： - 该图为一个简单图（不循环且不包含多重边）； - 三元组中每对 $u,v$ 不重复。 ### 输出格式 一个整数，为“有用边”的数量。 ### 说明/提示 在第一个样例中，除了权重为 5 的边外，每条边都是有用边。 在第二个样例中，只有 1 和 2 之间的边是有用的，因为它属于路径 1-2 和 $10≤11$。3和4之间的边是没有用的。 在第三个样例中，两条边都是有用的，因为路径 $1-2-3-2$ 的长度正好为 5。 请注意，路径可能会多次通过一个顶点。 翻译者：[XiaoQuQu](https://www.luogu.com.cn/user/427623)

题目描述

You are given a weighted undirected graph on $ n $ vertices along with $ q $ triples $ (u, v, l) $ , where in each triple $ u $ and $ v $ are vertices and $ l $ is a positive integer. An edge $ e $ is called useful if there is at least one triple $ (u, v, l) $ and a path (not necessarily simple) with the following properties: - $ u $ and $ v $ are the endpoints of this path, - $ e $ is one of the edges of this path, - the sum of weights of all edges on this path doesn't exceed $ l $ . Please print the number of useful edges in this graph.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 2\leq n\leq 600 $ , $ 0\leq m\leq \frac{n(n-1)}2 $ ). Each of the following $ m $ lines contains three integers $ u $ , $ v $ and $ w $ ( $ 1\leq u, v\leq n $ , $ u\neq v $ , $ 1\leq w\leq 10^9 $ ), denoting an edge connecting vertices $ u $ and $ v $ and having a weight $ w $ . The following line contains the only integer $ q $ ( $ 1\leq q\leq \frac{n(n-1)}2 $ ) denoting the number of triples. Each of the following $ q $ lines contains three integers $ u $ , $ v $ and $ l $ ( $ 1\leq u, v\leq n $ , $ u\neq v $ , $ 1\leq l\leq 10^9 $ ) denoting a triple $ (u, v, l) $ . It's guaranteed that: - the graph doesn't contain loops or multiple edges; - all pairs $ (u, v) $ in the triples are also different.

输出格式

Print a single integer denoting the number of useful edges in the graph.

输入输出样例

输入样例 #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

说明

In the first example each edge is useful, except the one of weight $ 5 $ . In the second example only edge between $ 1 $ and $ 2 $ is useful, because it belongs to the path $ 1-2 $ , and $ 10 \leq 11 $ . The edge between $ 3 $ and $ 4 $ , on the other hand, is not useful. In the third example both edges are useful, for there is a path $ 1-2-3-2 $ of length exactly $ 5 $ . Please note that the path may pass through a vertex more than once.

题意翻译

### 题目描述 先有一 $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 \dfrac{n(n-1)}{2}$）. 接下来 $m$ 行，每行三个整数 $u$，$v$ 与 $w$ （$1 \leq u$，$v \leq n$，$1 \leq w \leq 10^9$）。表示连接顶点 $u$ 和 $v$ 的边权重为 $w$。 接下来一行一个整数 $q$ （$1 \leq q \leq \dfrac{n(n-1)}{2} $），表示三元组的数量。 接下来 $q$ 行，每行三个整数 $u$，$v$ 与 $l$ （$1 \leq u$，$v \leq n$，$u \ne v$，$1 \leq l \leq 10^9$ ），表示三元组 $u,v,l$。 输入保证： - 该图为一个简单图（不循环且不包含多重边）； - 三元组中每对 $u,v$ 不重复。 ### 输出格式 一个整数，为“有用边”的数量。 ### 说明/提示 在第一个样例中，除了权重为 5 的边外，每条边都是有用边。 在第二个样例中，只有 1 和 2 之间的边是有用的，因为它属于路径 1-2 和 $10≤11$。3和4之间的边是没有用的。 在第三个样例中，两条边都是有用的，因为路径 $1-2-3-2$ 的长度正好为 5。 请注意，路径可能会多次通过一个顶点。 翻译者：[XiaoQuQu](https://www.luogu.com.cn/user/427623)