12/25 PKU

1724 ROADS

辺に距離とコストがあるグラフが与えられる。コストの和をK以下の経路の中で、距離が最短のものを求めよ。

[頂点][使ったコスト]でDijkstra

1986 Distance Queries

木が与えられる。2頂点間の距離を求めるクエリをK個オフライン処理せよ。

Tarjan を使って最小共通先祖を各クエリに対して求める。すると、根からの距離をdepth[p] と置くとdist(p, q) = depth[p] + depth[q] - 2depth[LCA(p, q)]で求まる。
Spaghetti Sourceを読むとLCAは線形で解けるようなことが書いてあるんですがどうするんでしょうか。ちなみにTarjanはunion findを定数とみなすなら線形のようです。

3402 Add a queen

盤面にいくつかクイーンが置かれている。まだ置かれていないある１マスにクイーンを置く。このとき、クイーンによって攻撃されないマスの数が最大になるようにクイーンを置くが、そのとき置く場所を求めよ。複数ある場合は、辞書順最小のものを求めよ。

基本的にはやるだけだが、「辞書順最小」なので、(r, w)のpairを作って比較するとWAになる。(a1 < a10 < a11 < … < a2 < a20 < …)