题目详情题解（0）讨论（0）提交记录（0）

CF1482F.Useful Edges

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个有 nn 个顶点的带权无向图，以及 qq 个三元组 (u,v,l)(u, v, l)，其中每个三元组中 uu 和 vv 是顶点，ll 是一个正整数。对于一条边 ee，如果存在至少一个三元组 (u,v,l)(u, v, l) 和一条路径（不一定简单路径），满足以下条件：

  • uu 和 vv 是该路径的两个端点，
  • ee 是该路径上的一条边，
  • 该路径上所有边的权值之和不超过 ll，

则称这条边 ee 是有用的。

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

输入格式

第一行包含两个整数 nn 和 mm（2≤n≤6002\leq n\leq 600，0≤m≤n(n−1)20\leq m\leq \frac{n(n-1)}{2}）。

接下来的 mm 行，每行包含三个整数 uu、vv 和 ww（1≤u,v≤n1\leq u, v\leq n，u≠vu\neq v，1≤w≤1091\leq w\leq 10^9），表示一条连接顶点 uu 和 vv 的权值为 ww 的边。

接下来一行包含一个整数 qq（1≤q≤n(n−1)21\leq q\leq \frac{n(n-1)}{2}），表示三元组的数量。

接下来的 qq 行，每行包含三个整数 uu、vv 和 ll（1≤u,v≤n1\leq u, v\leq n，u≠vu\neq v，1≤l≤1091\leq l\leq 10^9），表示一个三元组 (u,v,l)(u, v, l)。

保证：

  • 图中没有自环和重边；
  • 所有三元组中的 (u,v)(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

说明/提示

在第一个样例中，除了权值为 55 的那条边外，其余每条边都是有用的。

在第二个样例中，只有 11 和 22 之间的边是有用的，因为它属于路径 1−21-2，且 10≤1110\leq 11。而 33 和 44 之间的边则不是有用的。

在第三个样例中，两条边都是有用的，因为存在一条长度恰好为 55 的路径 1−2−3−21-2-3-2。注意，路径可以经过某个顶点多次。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页