AOJ 2454 : Repairing
問題↓
問題概要
- 線分が与えられます。
- source と sink となる点が与えれます。
- sorce から sink 線分に沿って水を流します。
- 途中に stopper という点がいくつか存在します。
- stopperを〆ることでそこで水の流れを止めることができます。
- 止まる水の流れる最小の距離を求めて下さい。
解法
- セグメントアレンジメント
- 幅優先でsinkから行けるstopperまでを全部フラグたてる
- 幅優先でsorceからフラグのたってない場所の線分の長さを数える
- 線分の長さの総和から上記を引く
ソースコード
感想
スパソの幾何ライブラリを改変しました。 隣接行列表現だとまずいので、隣接リスト表現するようにしました。
