ABC051 D Candidates of No Shortest Paths
D Candidates of No Shortest Paths
所見
ワーシャルフロイド+ちょっと。更新される辺の数え方を間違えて1WAしたけど40分なので本番でも解けるだろうか。
ワーシャルフロイド周りのバグり方に詳しくなっていくのを感じる(？)
問題概要
自己ループと二重辺を含まない N 頂点 M 辺の重み付き無向連結グラフが与えられる。このグラフのうち、どの2点間の最短経路にも含まれない辺の数を求めよ。
取った方針
全点対最短距離なのでワーシャルフロイドを使うことを考える。
使うと、ワーシャルフロイドにおいて更新が起きる点間にある辺は使われない辺であることがわかる。これは、更新が起きるということはそこに張られている辺を通るよりもコストの低いパスが存在するということであり、最短経路を通るためにはそちらのパスを通る必要があるからである。
ワーシャルフロイドをしながらそのような辺を数えればよいので、O(N3)となり通る。
一度更新が起きる度にansをインクリメントしてバグらせた。これは、一つの辺について更新は何度も起きる可能性があるため。
正しい方針(解説に載っていた方針)
まず私の方針同様ワーシャルフロイドもしくはダイクストラで全点対の最短距離を求める。
dist(i,j)でiからjまでの最短距離、edge(i,j)でiからjに張られるエッジのコストを表すことにすると、最短経路に含まれるエッジはある点の組s,tについて以下の等式を満たす。
dist(s,i) + edge(i,j) + dist(j,t) = dist(s,t)
この式は、s->iの最短距離+i->jに張られる辺のコスト+j->tの最短距離がs->tの最短距離となる場合、edge(i,j)はその最短経路に含まれる、というものであり、直感的である。
これをすべての辺についてすべてのs,tの組について行えば、どの辺が最短経路に含まれないかを調べることができる。(全探索)
この計算量はO(MN2)である。
得られた知見
・edge(i,j) < dist(i,k) + dist(k,j)なる点kが存在する場合、edge(i,j)が最短経路に含まれることはない。(私の解法)
・辺(i,j)について、 dist(s,i) + edge(i,j) + dist(j,t) = dist(s,t) なるs,tが存在する場合、その辺(i,j)はsからtへの最短経路に含まれる。(公式解法)
・ワーシャルフロイドは一つの点対の最短距離が複数回更新されることがあることを忘れない。
・i->jに辺が張ってあるかを「G[i][j]がINFでないか」と判定するとバグる。(理由:辺が張られていない点対も最初は重みがINFであるが、パスが一つでも見つかればINFでなくなるため)
解くのに必要な要素
・グラフ上の最短経路アルゴリズム(ダイクストラ/ワーシャルフロイド)
・「任意の点対の最短経路に含まれない辺」の定式化(その辺より重みの軽いパスの存在 or dist(s,i) + edge(i,j) + dist(j,t) = dist(s,t) なるs,tの存在)
周辺調査によって得られた知見
特になし
