E - Edge Deletion Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点 M 辺の単純連結無向グラフが与えられます。
辺 i は頂点 A_i と頂点 B_i を結ぶ長さ C_i の辺です。

以下の条件を満たすようにいくつかの辺を削除します。削除する辺の数の最大値を求めてください。

  • 辺を削除した後のグラフも連結である。
  • 全ての頂点対 (s,t) について、頂点 s と頂点 t の間の距離が削除前と削除後で変化しない。

注釈

単純連結無向グラフとは、単純かつ連結で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。
グラフが連結であるとは、グラフ上の任意の 2 頂点 s, t について s から t へ辺をたどって行けることをいいます。
頂点 s と頂点 t の間の距離とは、頂点 s と頂点 t の間の最短路の長さのことをいいます。

制約

  • 2 \leq N \leq 300
  • N-1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i \lt B_i \leq N
  • 1 \leq C_i \leq 10^9
  • i \neq j ならば (A_i, B_i) \neq (A_j, B_j) である。
  • 与えられるグラフは連結である。
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M

出力

答えを出力せよ。

入力例 1

3 3
1 2 2
2 3 3
1 3 6

出力例 1

1

辺を削除する前の全ての頂点対の距離は次の通りです。

  • 頂点 1 と頂点 2 の距離は 2
  • 頂点 1 と頂点 3 の距離は 5
  • 頂点 2 と頂点 3 の距離は 3

辺 3 を削除しても全ての頂点間の距離は変化しません。また、問題文の条件を満たすように 2 本以上の辺を削除することはできないので、答えは 1 本になります。

入力例 2

5 4
1 3 3
2 3 9
3 5 3
4 5 3

出力例 2

0

どの辺も削除することができません。

入力例 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

出力例 3

5

Score : 500 points

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges.
Edge i connects Vertex A_i and Vertex B_i, and has a length of C_i.

Let us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.

  • The graph is still connected after the deletion.
  • For every pair of vertices (s, t), the distance between s and t remains the same before and after the deletion.

Notes

A simple connected undirected graph is a graph that is simple and connected and has undirected edges.
A graph is simple when it has no self-loops and no multi-edges.
A graph is connected when, for every pair of two vertices s and t, t is reachable from s by traversing edges.
The distance between Vertex s and Vertex t is the length of a shortest path between s and t.

Constraints

  • 2 \leq N \leq 300
  • N-1 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq A_i \lt B_i \leq N
  • 1 \leq C_i \leq 10^9
  • (A_i, B_i) \neq (A_j, B_j) if i \neq j.
  • The given graph is connected.
  • All values in input are integers.

Input

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

Output

Print the answer.

Sample Input 1

3 3
1 2 2
2 3 3
1 3 6

Sample Output 1

1

The distance between each pair of vertices before the deletion is as follows.

  • The distance between Vertex 1 and Vertex 2 is 2.
  • The distance between Vertex 1 and Vertex 3 is 5.
  • The distance between Vertex 2 and Vertex 3 is 3.

Deleting Edge 3 does not affect the distance between any pair of vertices. It is impossible to delete two or more edges while satisfying the condition, so the answer is 1.

Sample Input 2

5 4
1 3 3
2 3 9
3 5 3
4 5 3

Sample Output 2

0

No edge can be deleted.

Sample Input 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

Sample Output 3

5