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.