100 atcoder#ABC051D. [ABC051D] Candidates of No Shortest Paths

[ABC051D] Candidates of No Shortest Paths

题目描述

自己ループと二重辺を含まない N N 頂点 M M 辺の重み付き無向連結グラフが与えられます。
i (1iM) i\ (1≦i≦M) 番目の辺は頂点 ai a_i と頂点 bi b_i を距離 ci c_i で結びます。
ここで、自己ループは ai = bi (1iM) a_i\ =\ b_i\ (1≦i≦M) となる辺のことを表します。
また、二重辺は (ai,bi)=(aj,bj) (a_i,b_i)=(a_j,b_j) または (ai,bi)=(bj,aj) (1i < jM) (a_i,b_i)=(b_j,a_j)\ (1≦i\ <\ j≦M) となる辺のことを表します。
連結グラフは、どの異なる 2 2 頂点間にも経路が存在するグラフのことを表します。
どの異なる 2 2 頂点間の、どの最短経路にも含まれない辺の数を求めてください。

输入格式

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

N N M M a1 a_1 b1 b_1 c1 c_1 a2 a_2 b2 b_2 c2 c_2 : : aM a_M bM b_M cM c_M

输出格式

グラフ上の、どの異なる 2 2 頂点間の、どの最短経路にも含まれない辺の数を出力せよ。

题目大意

给定一个 nn 个点,mm 条边的无重边无自环的加权无向连通图,问全源最短路有几条边没被用到。

3 3
1 2 1
1 3 1
2 3 3
1
3 2
1 2 1
2 3 1
0

提示

制約

  • 2N100 2≦N≦100
  • N1Mmin(N(N1)/2,1000) N-1≦M≦min(N(N-1)/2,1000)
  • 1ai,biN 1≦a_i,b_i≦N
  • 1ci1000 1≦c_i≦1000
  • ci c_i は整数である。
  • 与えられるグラフは自己ループと二重辺を含まない。
  • 与えられるグラフは連結である。

Sample Explanation 1

この入力例で与えられるグラフにおける、全ての異なる 2 2 頂点間の最短経路は以下の通りです。 - 頂点 1 1 から頂点 2 2 への最短経路は、頂点 1 1 → 頂点 2 2 で経路長は 1 1 - 頂点 1 1 から頂点 3 3 への最短経路は、頂点 1 1 → 頂点 3 3 で経路長は 1 1 - 頂点 2 2 から頂点 1 1 への最短経路は、頂点 2 2 → 頂点 1 1 で経路長は 1 1 - 頂点 2 2 から頂点 3 3 への最短経路は、頂点 2 2 → 頂点 1 1 → 頂点 3 3 で経路長は 2 2 - 頂点 3 3 から頂点 1 1 への最短経路は、頂点 3 3 → 頂点 1 1 で経路長は 1 1 - 頂点 3 3 から頂点 2 2 への最短経路は、頂点 3 3 → 頂点 1 1 → 頂点 2 2 で経路長は 2 2 したがって、一度も最短経路として使用されていない辺は、頂点 2 2 と頂点 3 3 を結ぶ長さ 3 3 の辺のみであるため、1 1 を出力します。

Sample Explanation 2

全ての辺が異なる 2 2 頂点間のある最短経路で使用されます。