#ABC243E. 全源最短路生成图的最少边数
全源最短路生成图的最少边数
题目描述
给定一个有 个顶点、 条边的简单带权无向连通图,顶点编号为 ,所有边权均为正整数。
可以删除若干条边,但删除后的图必须仍然连通,且任意两个顶点之间的最短距离必须与删除前相同。
请计算最多可以删除多少条边。输出的是删除的边数,不是最终保留的边数。
输入格式
第一行输入两个整数 $n,m\left(2\leqq n\leqq300;\ n-1\leqq m\leqq n(n-1)/2\right)$。
此后 行,每行输入三个整数 $u_i,v_i,w_i\left(1\leqq u_i<v_i\leqq n;\ 1\leqq w_i\leqq10^9\right)$,代表一条无向边。
不同边的端点对互不相同,保证图连通。
输出格式
输出一个整数,代表在保持所有顶点对最短距离不变的条件下,最多可以删除的边数。
测试样例
3 3
1 2 2
2 3 3
1 3 6
1
样例 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