Candidates of No Shortest Paths

AtCoder

IDabc051_d

Time2000ms

Memory256MB

Difficulty—

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. ## 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. ## 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$ $:$ $a_M$ $b_M$ $c_M$ [samples]

Samples

Input #1

Output #1

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$.

Input #2

3 2
1 2 1
2 3 1

Output #2

0

Every edge is contained in some shortest path between some pair of different vertices.

API Response (JSON)

{
  "problem": {
    "name": "Candidates of No Shortest Paths",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc051_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an undirected connected weighted graph with $N$ vertices and $M$ edges that contains neither self-loops nor double edges.  \nThe $i$\\-th $(1≤i≤M)$ edge connects vertex $a_i$ and vertex $b...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments