問題概要
グラフとクエリが与えられる。それぞれのクエリで指定されたただ1つの頂点Kを通過して頂点aから頂点bまでの最短経路長を求める。
atcoder.jp
解法
どうせa->KとK->bをいちいちdijkstraしていたのでは間に合わないのだろうなあという気持ちになる。
ここで、Kは各クエリで指定され直されるわけではないので前処理としてにKに対するdijkstraをかけておけばa->K->bまでの経路が速く求まる。
前処理はdijkstraで後はO(Q)。これを実装して、AC。
atcoder.jp
