AtCoderを参照. https://atcoder.jp/contests/arc083/tasks/arc083_b
まず実際に全部の頂点に記録通りに経路を引いたとして、最短の経路距離を求める. N は300以下なので Warshall-Floyd法を素直に実装すれば問題ない.
記録上の最短経路と、その辺を取り除いたときに実際に実現できる最短経路が同一か長い時に実現可能. ここで長い場合で実現可能なのは、特定のもののみ経路の重みを長くすることで、他の経路に影響せずに実現できるから.
そして、実際の最短経路を実現するような辺は別になくてもよい. その辺を取り除いても問題ない場合はそれでよい. それはワーシャルフロイドのアルゴリズムに該当するかを考慮することで可能.
この記事を書くにあたり、以下のコードを参考にしました. https://atcoder.jp/contests/arc083/submissions/4190487