ABC243E - Edge Deletion

考え方

全点対最短経路問題(すべての2頂点間の最短路を求める問題)が解けていれば,
  • ある2頂点を結ぶ辺は,
  • その2頂点を迂回する(複数の辺を使う)ことで,同じコスト「以下」で到達できるならなくてもよい(※1)
ことからこの問題も解ける.

全点対最短経路問題は,頂点数が少ないので,ワーシャル-フロイド法で間に合う.

※1:2頂点の2通り以上ある道の1コを消すだけなので連結性は保たれる.また,迂回したほうが早いのだから,この辺は他の最短経路使われていない(消す辺を通る代わりに迂回すればよい).

回答例

https://atcoder.jp/contests/abc243/editorial/3561d[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)