Candidates of No Shortest Paths

题目描述

给你一个无自环且无重边的无向连通加权图，图中有 $N$ 个顶点和 $M$ 条边。
第 $i$ 条 $(1≤i≤M)$ 边连接顶点 $a_i$ 和顶点 $b_i$，距离为 $c_i$。
这里，自环是指 $a_i = b_i (1≤i≤M)$ 的边，重边是指两条边满足 $(a_i,b_i)=(a_j,b_j)$ 或 (a_i,b_i)=(b_j,a_j) (1≤i<j≤M)。
连通图是指任意两个不同顶点之间都存在路径的图。
求图中不属于任意一对不同顶点之间任意最短路径的边的数量。

输入格式

输入从标准输入按以下格式给出： $N$ $M$
$a_1$ $b_1$ $c_1$
$a_2$ $b_2$ $c_2$ $:$
$a_M$ $b_M$ $c_M$

输出格式

输出图中不属于任意一对不同顶点之间任意最短路径的边的数量。

3 3
1 2 1
1 3 1
2 3 3

1

3 2
1 2 1
2 3 1

0

提示

$2≤N≤100$ $N-1≤M≤min(N(N-1)/2,1000)$ $1≤a_i,b_i≤N$ $1≤c_i≤1000$ $c_i$ 是整数。 给定的图没有自环也没有重边。 给定的图是连通的。在给定的图中，所有顶点对之间的最短路径如下：

从顶点 $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$。

因此，唯一一条不属于任何最短路径的边是连接顶点 $2$ 和顶点 $3$ 且长度为 $3$ 的那条边，所以输出应为 $1$。
每条边都属于某些不同顶点对之间的最短路径。

标签: AtCoder|abc051D

来源

AtCoder|abc051D