#ABC051D. 不在最短路中的边
不在最短路中的边
题目描述
给定一个有 个顶点、 条边的简单带权无向连通图。顶点编号为 ,每条边的权值均为正整数。
考虑任意两个不同顶点之间的所有最短路径。请统计从未出现在其中任何一条最短路径上的边数。
若一条边与其他路线长度相同,它仍可能出现在某条最短路径上,不能因此计入答案。
输入格式
第一行输入两个整数 $n,m\left(2\leqq n\leqq100;\ n-1\leqq m\leqq\min\{n(n-1)/2,10^3\}\right)$。
此后 行,每行输入三个整数 $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)$,代表一条无向边。
保证图连通,没有自环和重边。
输出格式
输出一个整数,代表从未被任何顶点对的任何最短路径使用过的边数。
测试样例
3 3
1 2 1
1 3 1
2 3 3
1
样例 1 解释
顶点 与 之间经顶点 的路线长度为 ,比它们之间长度为 的直接边更短。因此这条直接边不会出现在任何最短路径上,答案为 。另两条边分别是其端点之间的最短路径。
3 2
1 2 1
2 3 1
0