Edge Deletion

题目描述

给你一个有 $N$ 个顶点和 $M$ 条边的简单连通无向图。
边 $i$ 连接顶点 $A_i$ 和顶点 $B_i$，并且长度为 $C_i$。 我们要删除若干条边，满足下面的条件。求最多可以删除的边数。

删除后图仍然是连通的。 对于任意一对顶点 $(s, t)$，删除前后 $s$ 和 $t$ 之间的距离保持不变。

输入格式

输入从标准输入按照以下格式给出： $N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

输出格式

输出答案。

3 3
1 2 2
2 3 3
1 3 6

1

5 4
1 3 3
2 3 9
3 5 3
4 5 3

0

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

5

提示

$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$. 给定的图是连通的。 输入中的所有数值均为整数。简单连通无向图是指图是简单的并且连通且边为无向边。
当图没有自环且没有重边时，图是简单的。
当对于任意一对顶点 $s$ 和 $t$，可以通过遍历边从 $s$ 到达 $t$ 时，图是连通的。
顶点 $s$ 和顶点 $t$ 之间的距离是 $s$ 到 $t$ 的最短路径的长度。删除前每一对顶点之间的距离如下。

顶点 $1$ 和顶点 $2$ 之间的距离是 $2$。 顶点 $1$ 和顶点 $3$ 之间的距离是 $5$。 顶点 $2$ 和顶点 $3$ 之间的距离是 $3$。

删除边 $3$ 不会影响任意一对顶点之间的距离。要满足条件不可能删除两条或更多条边，所以答案是 $1$。
没有边可以被删除。

标签: AtCoder|abc243E

来源

AtCoder|abc243E