#ABC051D. 不在最短路中的边

不在最短路中的边

题目描述

\hspace{15pt}给定一个有 nn 个顶点、mm 条边的简单带权无向连通图。顶点编号为 1∼n1\sim n,每条边的权值均为正整数。

\hspace{15pt}考虑任意两个不同顶点之间的所有最短路径。请统计从未出现在其中任何一条最短路径上的边数。

\hspace{15pt}若一条边与其他路线长度相同,它仍可能出现在某条最短路径上,不能因此计入答案。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(2\leqq n\leqq100;\ n-1\leqq m\leqq\min\{n(n-1)/2,10^3\}\right)$。

\hspace{15pt}此后 mm 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i;\ 1\leqq w_i\leqq10^3\right)$,代表一条无向边。

\hspace{15pt}保证图连通,没有自环和重边。

输出格式

\hspace{15pt}输出一个整数,代表从未被任何顶点对的任何最短路径使用过的边数。

测试样例

3 3
1 2 1
1 3 1
2 3 3
1

样例 1 解释

\hspace{15pt}顶点 22 与 33 之间经顶点 11 的路线长度为 22,比它们之间长度为 33 的直接边更短。因此这条直接边不会出现在任何最短路径上,答案为 11。另两条边分别是其端点之间的最短路径。

3 2
1 2 1
2 3 1
0