问题 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(条)。