AOJ-2249 : Road Construction

問題概要

ノード数V(<10000)、辺数E(<20000)の重み付き無向グラフが与えられる。0を根としたshortest path treeのうちコスト最小のものを求める問題。

解法

Dijkstraした後距離の近い順にソートして確定させていく。

UVa-11085 : Back to the 8-Queens

問題概要

8クイーンの正しくないかもしれない配置が与えられる(ただし、各行はちがうことが保証されている)。正しい状態にするには最低幾つ動かす必要があるか求める問題。

解法

n=8だったらnクイーンの全探索は余裕を持って間に合うので解を全て生成して距離を求める。解は92個しかないので埋め込んでも良い。