M-SOLUTIONS プロコンオープン 2020 E - M's Solution

問題：E - M's Solution

解答：Submission #15474499 - M-SOLUTIONS Programming Contest 2020

解法：追加する線路は集落を通るとしてよい。集落を通らない線路は「移動させてもコストが変わらない」「片方に移動させるとコスト増、もう片方に移動させるとコスト減」のいずれかであり、どちらの場合もコストを増加させずに線路を集落上に移動させることができる。

各集落ごとに「線路が通らない」「南北方向の線路が通る」「東西方向の線路が通る」の3通りの線路の通り方をそれぞれ試す全探索を実施し、その際に追加された線路の本数ごとにコストの最小値を記録しておき、それを更新すればよい。

全探索内でのコスト計算は、各集落ごとにコストを逐一計算すると間に合わない。事前に各集落、各線路のパターンに対するコストの最小値を計算しておくと計算量削減となる。