3/15 PKU - Algorithmer’s note

モンスターが何体かいる。1からMまでの数字が書かれた箱もある。モンスターに箱を渡すと、モンスターは攻撃してこない。渡さなければ、攻撃してくる。モンスターごとに、渡せる箱の数値の上限がある。モンスターごとに、攻撃されたときのダメージがある。ダメージの和を最小化せよ。

数値の上限でソートして、上限が大きいほうからpriority_queueに突っ込んで、各タイミングで最大のものをpopして、最後まで残っているものの和を求める。

迷路を調査隊が調査する。起点から歩いて、迷路上にあるすべてのモンスターを確認したい。調査隊は、起点もしくは、モンスターを確認した際に分割できる。調査コストは、調査隊のグループが歩いた距離の和である（まとまって歩いていたら何人いてもコストは同じ）。コストの和の最小値を求めよ。

スタートとモンスターを同一視して、モンスター間の距離をBFSで求める。その後最小全域木。