2012-07-11から1日間の記事一覧
問題概要 重み付き無向グラフが与えられる。0からN-1までの経路のうちK+1番目に大きい値を最小化したい。最小値を求める問題。 解法 解について二分探索する。判定関数は、コストx以上なら1、それ以外なら0を重みとして0からN-1までの最短路がK以下になるか…
問題概要 重み付き無向グラフが与えられる。0からN-1までの経路のうちK+1番目に大きい値を最小化したい。最小値を求める問題。 解法 解について二分探索する。判定関数は、コストx以上なら1、それ以外なら0を重みとして0からN-1までの最短路がK以下になるか…