ABC243 E - Edge Deletion (500)

コンテスト中の考察

ワーシャルフロイド法で各点間の最短距離を求める

各辺について端点の内どちらかを始点にしてダイクストラ法をする

最短距離が更新されてたらその辺は使わない

距離が更新されなくても2本で行けたら消せるのに区別していないので駄目

2本以上で同じ長さに分割できたら消せるのにその区別法について気付いてなかった

解説の方法

ワーシャルフロイド法で各点間の最短距離を求める

各辺についてどこかの点を経由して同じ長さ以下にできるなら今の辺を削除できる

2本以上の場合と場合分けになっている