考え方
全点対最短経路問題(すべての2頂点間の最短路を求める問題)が解けていれば,- ある2頂点を結ぶ辺は,
- その2頂点を迂回する(複数の辺を使う)ことで,同じコスト「以下」で到達できるならなくてもよい(※1)
全点対最短経路問題は,頂点数が少ないので,ワーシャル-フロイド法で間に合う.
※1:2頂点の2通り以上ある道の1コを消すだけなので連結性は保たれる.また,迂回したほうが早いのだから,この辺は他の最短経路使われていない(消す辺を通る代わりに迂回すればよい).
回答例
https://atcoder.jp/contests/abc243/editorial/3561はd[i][i]
をINFで初期化している.ゼロで初期化する場合は,最後の処理で$i = a, b$(迂回時に通る頂点)になる場合を避ける必要がある.
N, M = map(int, input().split()) E = [] for _ in range(M): a, b, c = map(int, input().split()) E.append((a - 1, b - 1, c)) d = [[1 << 60] * N for _ in range(N)] for i in range(N): d[i][i] = 0 for a, b, c in E: d[a][b] = c d[b][a] = c for k in range(N): for i in range(N): for j in range(N): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) ans = 0 for a, b, c in E: for i in range(N): if i == a or i == b:continue if c >= d[a][i] + d[i][b]: ans += 1 break print(ans)