AT_abc051_d [ABC051D] Candidates of No Shortest Paths

给定一个 $N$ 个顶点 $M$ 条边的带权无向连通图，图中不包含自环和重边。 第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$，距离为 $c_i$。 这里，自环指的是 $a_i = b_i$ 的边。 重边指的是存在 $i < j$，使得 $(a_i, b_i) = (a_j, b_j)$ 或 $(a_i, b_i) = (b_j, a_j)$ 的边。 连通图指的是任意两个不同的顶点之间都存在路径的图。 请你求出，在所有不同的 $2$ 个顶点之间的所有最短路径中，从未被使用过的边的数量。

输入以以下格式从标准输入读入。 > $N$ $M$ > $a_1$ $b_1$ $c_1$ > $a_2$ $b_2$ $c_2$ > $\vdots$ > $a_M$ $b_M$ $c_M$

输出在图中，从未被任何一对不同顶点之间的最短路径使用过的边的数量。

## 限制条件 - $2 \leq N \leq 100$ - $N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 1000\right)$ - $1 \leq a_i, b_i \leq N$ - $1 \leq c_i \leq 1000$ - $c_i$ 是整数。 - 给定的图不包含自环和重边。 - 给定的图是连通的。 ## 样例解释 1 对于本输入样例给出的图，所有不同的 $2$ 个顶点之间的最短路径如下： - 从顶点 $1$ 到顶点 $2$ 的最短路径为 $1 \to 2$，路径长度为 $1$ - 从顶点 $1$ 到顶点 $3$ 的最短路径为 $1 \to 3$，路径长度为 $1$ - 从顶点 $2$ 到顶点 $1$ 的最短路径为 $2 \to 1$，路径长度为 $1$ - 从顶点 $2$ 到顶点 $3$ 的最短路径为 $2 \to 1 \to 3$，路径长度为 $2$ - 从顶点 $3$ 到顶点 $1$ 的最短路径为 $3 \to 1$，路径长度为 $1$ - 从顶点 $3$ 到顶点 $2$ 的最短路径为 $3 \to 1 \to 2$，路径长度为 $2$ 因此，从未被任何最短路径使用过的边只有连接顶点 $2$ 和顶点 $3$，长度为 $3$ 的那一条，所以输出 $1$。 ## 样例解释 2 所有的边都被某一对不同顶点之间的最短路径使用过。 由 ChatGPT 4.1 翻译