オンサイトで未確認

ukuku09の活動記録。

AtCoder Beginner Contest 051 D: Candidates of No Shortest Paths

ABC埋め中。

 

問題文

abc051.contest.atcoder.jp

解法

Warshall-Floyd で全頂点間の最短経路を求めて、与えられたエッジの端点間の最短経路重みがエッジの重みより小さくなっているかどうかを判定するだけで、そのエッジがグラフ上のいずれかの最短経路上に含まれているかどうかがわかる。

ある辺 i の端点を ai, bi、辺の重みを ci とすると、ai-bi 間の最短経路の重みは $x \leq c_i$ を満たす。$x = c_i$ の時、辺 i は ai-bi 間の最短経路になりうる。$x < c_i$ の時、明らかに ai-bi 間の最短経路に辺 i は含まれない。また、グラフ上のある2頂点 ui, vi 間に辺 i を含む最短経路がある仮定すると、その重みはある整数 w を用いて $w + c_i$ と表すことができる。しかし、ai-bi 間の最短経路の重みは $x < c_i$ より、 $w + x < w + c_i$ なので、辺 i を ai-bi 間の最短経路に置き換えることでより短い経路を得ることができる。これは仮定に反するので、ai-bi 間の最短経路が辺 i を含まない時、グラフ上のどの2頂点間の最短経路上にも辺 i は含まれないと言える(数学ができないのでガバガバ証明でごめんなさい)。

計算量は Warshall-Floyd が一番重くて $O(N^3)$。最後の判定の仕方が頭悪くてN2回してるのは秘密。