1. 問題
 特殊隊員たちが決められた建物からスタート。彼らが分かれて、隣接道路を使い、隣の建物に到達しその建物を爆破する。ただし、最後にまたある決められた建物に彼らが戻ってこないといけない。隣接道路の移動時間は1時間単位とし、全部の建物を破壊するのに必要な最小移動時間を算出せよ。

2. 入力データの意味
 理解を深めるために、以下の例を考える。

この例での答えは4だ。グラフを見れば容易に納得するだろう。

p11463.jpg

 つまり、建物0からスタートし、建物1に到着し破壊する。建物3は集合地なので、まず建物2に到着して破壊した上、また建物1の地点に戻ってくる。最後に建物3につく。
 移動時間は0→1→2→1→3の4になる。

3. 考え方
 すべてのノード(建物)nに対し、スタートノードsからの最短距離x(n)と、エンドノードeからの最短距離y(n)を求める。
 すべてのnに対し、x(n)+y(n)の最大値が答えになるのだ。

最短距離を求めるのに、以下のような横型探索を使う。

道路に相当する隣接行列a[100][100]では、ノードu, vに道路あれば、
   a[u][v]=a[v][u]=1。
スタートノードsからの最短距離を配列dis[n](つまり、上記のx(n)に相当)とする。

(1) 初期値:すべてのノードnに対し、dis[n]=-1。
(2) スタートノードsに対し、dis[s]=0、sをキューに入れる。
(3) キューからノードを取り出す。ノードがなければ横型探索終了。ノードあれば、ノード名をnとする。
(4) すべてのノードm(0<=m<N)に対し、
  dis[m]=dis[n]+1 if a[n][m]==1 かつ dis[m]<0
  ノードmをキューに入れる。

横型探索終了した時点で、dis[n]にスタートノードsからの最短距離が記録される。

同じことをエンドノードeに対しても行う。

4. 感想
 1回目の提出ではバグあったが、2回目ではAC。実行時間は0.400秒だった。0.300秒に上げたいけど、それ以上のいいアイデアは浮かんでこない。

テクニック的に上げるなら、scanf()をやめるぐらいかな。気を取り直して、データ入力に自作の関数を使い、3回目の提出では0.1000秒に上がった。現時点では2位。

Comments are closed.

Post Navigation