← 返回题目列表

AtCoder · abc051_d

D. 无最短路径的候选者

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个无向连通加权图 N 顶点和 M 既不包含自循环也不包含双边的边。
的 i-th (1≤i≤M) 边连接顶点 a_i 和顶点 b_i 距离为 c_i.
这里,一个 自循环 是一条边,其中 a_i = b_i (1≤i≤M),和 双边缘 是两条边,其中 (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).
A 连通图 是一个图,其中每对不同顶点之间都有一条路径。
查找不包含在任意一对不同顶点之间的任何最短路径中的边的数量。

约束

  • 2≤N≤100
  • N-1≤M≤min(N(N-1)/2,1000)
  • 1≤a_i,b_i≤N
  • 1≤c_i≤1000
  • c_i 是一个整数。
  • 给定的图既不包含自环也不包含双边。
  • 给定的图形已连接。

输入

输入由标准输入按以下格式给出:

N M  
a_1 b_1 c_1  
a_2 b_2 c_2
:  
a_M b_M c_M  

输出

打印图中不包含在任意一对不同顶点之间的任何最短路径中的边的数量。


示例输入 1

3 3
1 2 1
1 3 1
2 3 3

示例输出 1

1

在给定的图中,所有不同顶点对之间的最短路径如下:

  • 从顶点开始的最短路径 1 到顶点 2 是:顶点 1 → 顶点 2,长度为 1.
  • 从顶点开始的最短路径 1 到顶点 3 是:顶点 1 → 顶点 3,长度为 1.
  • 从顶点开始的最短路径 2 到顶点 1 是:顶点 2 → 顶点 1,长度为 1.
  • 从顶点开始的最短路径 2 到顶点 3 是:顶点 2 → 顶点 1 → 顶点 3,长度为 2.
  • 从顶点开始的最短路径 3 到顶点 1 是:顶点 3 → 顶点 1,长度为 1.
  • 从顶点开始的最短路径 3 到顶点 2 是:顶点 3 → 顶点 1 → 顶点 2,长度为 2.

因此,唯一不包含在任何最短路径中的边是长度的边 3 连接顶点 2 和顶点 3,因此输出应该是 1.


示例输入 2

3 2
1 2 1
2 3 1

示例输出 2

0

每条边都包含在某对不同顶点之间的最短路径中。