ABC 144 F - Fork in the Road
解説を読みつつRubyだとTLEなのかな。とおもいつつclimpetさんがACしていて、コードゴルフじゃないC++のコードがあったので、そちらから読み解いてみた。
参考 : atcoder.jp
各頂点毎に辺を一つ潰したときと一つも潰さないときの1 -> Nへの期待パス長への差分の最小値を求めていて、差分を求めるために各頂点への遷移確率を使っていた。
時間計算量はO(M)で解いているっぽい。
元のグラフをG, 潰す辺 e = {s,t}、辺を一つ潰したグラフを G - e,
グラフ H上の i -> Nへの期待パス長を返す関数をf(H,i), 同じくグラフH上の1 -> sへの遷移確率をg(H,s)とすると下記の式で書けることになる。
f(G - e,1) = f(G,1) - g(G,s) * f(G,s) + g(G,s) * f(G - e, s)
期待パス長が(Pは1 -> Nへのパスの集合)になるので、sを通るパス集合と通らないパス集合に分けて考える。
sを通るパス集合のs以降の部分のみ、期待パス長に変化があるため、G上のs->Nへの期待パス長 * sへの遷移確率を引いて、G-e上のs->Nへの期待パス長 * sへの遷移確率を足すことで求まる。
sへの遷移確率はG,G-eも同じなので前処理でやはりO(M)で計算できる
それを踏まえた書いたコードが以下のリンク
