問題概要
重み付きの連結な双方向グラフがある。グラフの移動コストが$K$回与えられるので最後にいる頂点の候補を挙げろ。
$N\leqq10^2$、$M,K\leqq10^3$、$c(u,v)\leqq10^9$
解法
ダイクストラのようにじわじわ広げていきたい。
$dp[k][i]:=k$番目の移動経路で頂点$i$にいるかどうかをboolDPする。
計算量:$O(KM)$
| Home | About | Blogs | Tags | Categories | Algorithms | Archives |
重み付きの連結な双方向グラフがある。グラフの移動コストが$K$回与えられるので最後にいる頂点の候補を挙げろ。
$N\leqq10^2$、$M,K\leqq10^3$、$c(u,v)\leqq10^9$
ダイクストラのようにじわじわ広げていきたい。
$dp[k][i]:=k$番目の移動経路で頂点$i$にいるかどうかをboolDPする。
計算量:$O(KM)$