PKU

PKU
  1. PKU 3440 Coin Toss
  2. PKU 3439 Server Relocation

42問。

PKU 3440 Coin Toss

ひたすら計算する。Presentation Error食らったのは気のせい。

PKU 3439 Server Relocation

コンセントを頂点として、二コンセント間の距離がLENGTH1 + LENGTH2より小さいものの間に辺を引いたグラフにおいて、始点から終点までの最短経路を求めればよい。

単一始点だからDijkstraで決定だろｗｗｗｗｗｗｗｗｗｗ←アホ(俺)

求めるのは移動の「回数」であって、このグラフにある辺の重みはすべて1である(重みなし)。よってBFSを使ってO(|V|)で最小の移動回数を求めることができる。DijkstraだとTLEするよ！(経験者は語る)