competitive: ABC 021 C - 正直者の高橋くん

2019年4月29日月曜日

与えられたグラフの隣接行列を $A$ とするとき、 $a$ から $b$ への距離 $d$ のウォークの総数は $A^d$ の $a$ 列 $b$ 行に一致するので、これを最短距離について求めればよい。繰り返し二乗法をすれば計算量は ${\mathcal O}(n^3 \log n)$ 。¹

最短経路でDAGを作る話をまったく把握していなかったので、なんかおかしいなと思いながら知っている事実を使った。よく考えると、最短経路であることを何も活用していない。