Yukicoder092 逃走経路

問題概要

重み付きの連結な双方向グラフがある。グラフの移動コストが$K$回与えられるので最後にいる頂点の候補を挙げろ。

$N\leqq10^2$、$M,K\leqq10^3$、$c(u,v)\leqq10^9$

yukicoder092

解法

ダイクストラのようにじわじわ広げていきたい。
$dp[k][i]:=k$番目の移動経路で頂点$i$にいるかどうかをboolDPする。

計算量:$O(KM)$

ソース

https://yukicoder.me/submissions/253034

Share Comments
̃Gg[͂ĂȃubN}[Nɒlj
comments powered by Disqus