きままにものづくり

日々の気付いたことなんかを書いてます。

SRM626Div1Medium

問題

ノード数N、エッジ数Eの有向グラフが与えられる。ノードには1~Nまでの番号が振られている。各エッジは正整数コストを持っている。Nancyはノード1からスタートしノードNに最小コストで到達したい。Nancyはcharge回だけエッジのコストをマイナスにすることができる。この時の最小コストを求めよ。

解法

chargeを1回使った場合の最短距離をAとする。これは、ノードの数を二倍にし、コストwのuからvのエッジ(w,u,v)を(w,u,v)、(w,u+N,v+N)、(-w,u+N,v)と３つに分けることで計算できる。2回使った場合の最短距離 $D_2$ をA*Aと表す。実際の計算は $D_2(i,j) = min_k( A(i, k) + A(k, j) )$ となる。右辺はkを1~Nまで探索し、最小の値をとってくる演算となる。

計算量

$O(N^3 log C)$
N:ノード数
C:chargeの数

コード