きままにものづくり

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

SRM626Div2Hard

問題

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

解法

charge=0の時は、通常の最短経路問題となる。これを利用し、動的計画法で解いていく。xdlist[k][u]をメモとする。kはchargeの使用回数を示し、uは現在のノードの位置、xdlistは、k回のchargeを使用した際のuからNまでの最小コストを示す。

計算量

O(N*E*C)
N:ノード数
E:エッジ数
C:chargeの数

コード

広告を非表示にする