読者です 読者をやめる 読者になる 読者になる

AOJ 2454 : Repairing

問題↓

Repairing | Aizu Online Judge

問題概要

  • 線分が与えられます。
  • source と sink となる点が与えれます。
  • sorce から sink 線分に沿って水を流します。
  • 途中に stopper という点がいくつか存在します。
  • stopperを〆ることでそこで水の流れを止めることができます。 
  • 止まる水の流れる最小の距離を求めて下さい。

解法

  • セグメントアレンジメント
  • 幅優先でsinkから行けるstopperまでを全部フラグたてる
  • 幅優先でsorceからフラグのたってない場所の線分の長さを数える
  • 線分の長さの総和から上記を引く
ソースコード

感想

スパソの幾何ライブラリを改変しました。 隣接行列表現だとまずいので、隣接リスト表現するようにしました。