7070: ABC051 —— D - Candidates of No Shortest Paths
[Creator : ]
Description
You are given an undirected connected weighted graph with $N$ vertices and $M$ edges that contains neither self-loops nor double edges.
The $i$-th ($1≤i≤M$) edge connects vertex $a_i$ and vertex $b_i$ with a distance of $c_i$.
Here, a self-loop is an edge where $a_i = b_i\ (1≤i≤M)$, and double edges are two edges where $(a_i,b_i)=(a_j,b_j)$ or $(a_i,b_i)=(b_j,a_j)\ (1≤i<j≤M)$.
A connected graph is a graph where there is a path between every pair of different vertices.
Find the number of the edges that are not contained in any shortest path between any pair of different vertices.
The $i$-th ($1≤i≤M$) edge connects vertex $a_i$ and vertex $b_i$ with a distance of $c_i$.
Here, a self-loop is an edge where $a_i = b_i\ (1≤i≤M)$, and double edges are two edges where $(a_i,b_i)=(a_j,b_j)$ or $(a_i,b_i)=(b_j,a_j)\ (1≤i<j≤M)$.
A connected graph is a graph where there is a path between every pair of different vertices.
Find the number of the edges that are not contained in any shortest path between any pair of different vertices.
Input
The input is given from Standard Input in the following format:
$N\ M$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\vdots$
$a_M\ b_M\ c_M$
$N\ M$
$a_1\ b_1\ c_1$
$a_2\ b_2\ c_2$
$\vdots$
$a_M\ b_M\ c_M$
Output
Print the number of the edges in the graph that are not contained in any shortest path between any pair of different vertices.
Constraints
$2≤N≤100$
$N-1≤M≤min(N(N-1)/2,1000)$
$1≤a_i,b_i≤N$
$1≤c_i≤1000$
$c_i$ is an integer.
The given graph contains neither self-loops nor double edges.
The given graph is connected.
$N-1≤M≤min(N(N-1)/2,1000)$
$1≤a_i,b_i≤N$
$1≤c_i≤1000$
$c_i$ is an integer.
The given graph contains neither self-loops nor double edges.
The given graph is connected.
Sample 1 Input
3 3
1 2 1
1 3 1
2 3 3
Sample 1 Output
1
In the given graph, the shortest paths between all pairs of different vertices are as follows:
- The shortest path from vertex $1$ to vertex $2$ is: vertex $1$ → vertex $2$, with the length of $1$.
- The shortest path from vertex $1$ to vertex $3$ is: vertex $1$ → vertex $3$, with the length of $1$.
- The shortest path from vertex $2$ to vertex $1$ is: vertex $2$ → vertex $1$, with the length of $1$.
- The shortest path from vertex $2$ to vertex $3$ is: vertex $2$ → vertex $1$ → vertex $3$, with the length of $2$.
- The shortest path from vertex $3$ to vertex $1$ is: vertex $3$ → vertex $1$, with the length of $1$.
- The shortest path from vertex $3$ to vertex $2$ is: vertex $3$ → vertex $1$ → vertex $2$, with the length of $2$.
Thus, the only edge that is not contained in any shortest path, is the edge of length $3$ connecting vertex $2$ and vertex $3$, hence the output should be $1$.
Sample 2 Input
3 2
1 2 1
2 3 1
Sample 2 Output
0
Every edge is contained in some shortest path between some pair of different vertices.