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