貪欲解

まずは次のように頂点の出力強度を決定します。

• 各住民について、ランダムな順番に以下の操作を行う
  • 視聴可能になるための追加コストが最も低い頂点からの電波で視聴可能になるように出力強度を引き上げる

次に、各辺のON/OFFを決定します。
頂点 \(1\) と連結な頂点から出力強度が正の頂点へのパスの距離が最も小さいようなパスの各辺をONにすることを繰り返します。 これは、全点対最短路を事前計算しておき、該当するパスを優先度付きキューで管理することで効率的に計算できます。（プリム法）

山登り

上記の貪欲解は短時間で実行できるため、貪欲解を計算してから以下の操作を時間いっぱいまで繰り返します。

• 部分破壊：一部（1割くらい？）の頂点の出力強度を \(0\) にする
• 山登り：上記の貪欲解と同じように更新する

最後に、出力強度 \(5000\) 以内で視聴可能となる放送局と住民のペアを列挙しておく、必要な住民だけ更新するようにするなどの枝刈りを行うことで、 496M 点を取ることができました。 https://atcoder.jp/contests/ahc020/submissions/42196233