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の数
