问题 D: 跑图
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：350
解决：127
题目描述
给你一个N点M边的无向带权连通简单图（无向、带权、连通、无自环、无重边）
其中第i(1≤i≤M)条边连接点ai和bi，权重是ci
输出不属于任意两点的最短路径的边的条数。
其中第i(1≤i≤M)条边连接点ai和bi，权重是ci
输出不属于任意两点的最短路径的边的条数。
输入
- 2≤N≤100
- N-1≤M≤min(N(N-1)/2,1000)N−1≤M≤min(N(N−1)/2,1000)
- 1≤a_i,b_i≤N1≤ai,bi≤N
- 1≤c_i≤10001≤ci≤1000
- c_ici 是整数
- 给定的图没有自环也没有重边
- 给定的图是连通图
输入的格式是：
N M
a1 b1 c1
a2 b2 c2
...
am bm cm
输出
输出不属于任意两点的最短路径的边的条数。
即：如果点a和点b的最短路径经过了边c，那么c不是答案中的一条。
即：如果点a和点b的最短路径经过了边c，那么c不是答案中的一条。
样例输入 复制
3 3
1 2 1
1 3 1
2 3 3样例输出 复制
1提示
从点1到点2，最短路径是1->2，权重为1
从点2到点3，最短路径是2->3，权重为1
从点3到点1，最短路径是3->2->1，权重为2
所以第3条边（连接点1和点3，权重是3）不属于上面任何两点之间的最短路径，因此答案是1（条）。
从点2到点3，最短路径是2->3，权重为1
从点3到点1，最短路径是3->2->1，权重为2
所以第3条边（连接点1和点3，权重是3）不属于上面任何两点之间的最短路径，因此答案是1（条）。