分数: 500 点
问题陈述
给你一个简单的连通无向图 N 顶点和 M 边缘。
边缘 i 连接顶点 A_i 和顶点 B_i,长度为 C_i.
让我们在满足以下条件的同时删除一些边。求出可以删除的最大边数。
- 删除后图形仍然是连接的。
- 对于每对顶点 (s, t),之间的距离 s 和 t 删除前后保持不变。
注释
简单连通无向图是简单且连通且具有无向边的图。
当图没有自环和多边时,它是简单的。
对于每对两个顶点,图是连通的 s 和 t, t 可以从 s 通过遍历边。
顶点之间的距离 s 和顶点 t 是之间的最短路径的长度 s 和 t.
约束
- 2 \leq N \leq 300
- N-1 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i \lt B_i \leq N
- 1 \leq C_i \leq 10^9
- (A_i, B_i) \neq (A_j, B_j) if i \neq j.
- 给定的图形已连接。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
输出
打印答案。
示例输入 1
3 3 1 2 2 2 3 3 1 3 6
示例输出 1
1
删除前每对顶点之间的距离如下。
- 顶点之间的距离 1 和顶点 2 is 2.
- 顶点之间的距离 1 和顶点 3 is 5.
- 顶点之间的距离 2 和顶点 3 is 3.
删除边 3 不影响任何一对顶点之间的距离。在满足条件的情况下不可能删除两条或多条边,所以答案是 1.
示例输入 2
5 4 1 3 3 2 3 9 3 5 3 4 5 3
示例输出 2
0
无法删除任何边。
示例输入 3
5 10 1 2 71 1 3 9 1 4 82 1 5 64 2 3 22 2 4 99 2 5 1 3 4 24 3 5 18 4 5 10
示例输出 3
5