解法
ワーシャルフロイド法を用いてすべての頂点間の最短経路を求める。必要な辺はその辺を使わないと最短が達成できなくなる辺
証明
仮にその辺を使わないとすると、2辺以上を用いた最短経路が存在する。閉路に入る意味はないため、使われる変数は高々 。このうち、最も辺数の多い最短経路に着目すると、これに含まれる辺はすべて解法の条件に沿う辺である。なぜなら、これ以上変数は増えないから。
解法へのプロセス
ワーシャルフロイド法を知らないと、だいぶきつい。グラフ周りの問題は知識を前提としていることが多いため、知識を付けた方が取り組みやすそう。
また、本問のように必要条件を考えるとよい。しばしば十分条件となりうる。
